[PATCH dpdk/26.11 v4 0/2] graph: topological bitmap scheduling

[David Marchand]

On Thu, 15 Oct 2026 at 16:32, Robin Jarry <rjarry at redhat.com> wrote:
>
> Replace the FIFO circular buffer in rte_graph with a bitmap and a
> topologically-sorted schedule table. The old circular buffer appended
> nodes in enqueue order, effectively a partial DFS driven by per-node
> process functions. This caused convergence nodes to be visited before
> all upstream branches had run, resulting in redundant visits with
> smaller batches.
>
> Nodes are now sorted by (topo_order, node_id) using BFS depth from
> source nodes, ensuring upstream nodes are always visited before
> downstream ones. The diamond perf test shows a ~10% throughput
> improvement (converge visited once at 256 objs/call instead of twice
> at 128).
>
> Changes v3 -> v4:
>  - fixed check_includes error after RTE_PTR_ADD() changes
>  - s/__rte_always_inline/inline/ to fix checkpatch warnings
>  - removed entry from deprecation notice
>  - added release notes entries
>
> Changes v2 -> v3:
>  - dropped explicit priority field (int16_t) from rte_node_register
>    and struct node; topological ordering from BFS is sufficient
>  - removed hiprio worker node type from diamond test; topo_order
>    alone provides correct ordering without user intervention
>  - updated documentation and SVG diagram accordingly
>
> Changes v1 -> v2:
>  - split diamond perf test into separate preparatory patch
>  - added topological depth (topo_order) as secondary sort key to
>    preserve upstream-before-downstream ordering, preventing a
>    regression in the reverse tree test
>  - restored idx == 0 guard on bitmap set in the enqueue path to
>    avoid a ~15% throughput regression caused by touching the pending
>    bitmap cache line on every enqueue call
>  - added performance numbers measured before and after
>
> Cc: Christophe Fontaine <cfontain at redhat.com>
> Cc: David Marchand <david.marchand at redhat.com>
> Cc: Jerin Jacob <jerinj at marvell.com>
> Cc: Kiran Kumar Kokkilagadda <kirankumark at marvell.com>
> Cc: Konstantin Ananyev <konstantin.ananyev at huawei.com>
> Cc: Maxime Leroy <maxime at leroys.fr>
> Cc: Nithin Kumar Dabilpuram <ndabilpuram at marvell.com>
> Cc: Vladimir Medvedkin <vladimir.medvedkin at intel.com>
> Cc: Zhirun Yan <yanzhirun_163 at 163.com>
>
> Robin Jarry (2):
>   graph: add diamond topology performance test
>   graph: replace circular buffer with topological bitmap
>
>  app/test/test_graph_perf.c                    |  130 +-
>  doc/guides/prog_guide/graph_lib.rst           |   29 +-
>  .../prog_guide/img/graph_mem_layout.svg       | 1823 +++++++----------
>  doc/guides/rel_notes/deprecation.rst          |    8 -
>  doc/guides/rel_notes/release_26_11.rst        |   11 +
>  lib/graph/graph.c                             |   27 +-
>  lib/graph/graph_debug.c                       |   12 +-
>  lib/graph/graph_ops.c                         |   46 +
>  lib/graph/graph_populate.c                    |  107 +-
>  lib/graph/graph_private.h                     |   41 +-
>  lib/graph/rte_graph_model_mcore_dispatch.h    |   34 +-
>  lib/graph/rte_graph_model_rtc.h               |   63 +-
>  lib/graph/rte_graph_worker.h                  |    2 +-
>  lib/graph/rte_graph_worker_common.h           |   80 +-
>  14 files changed, 1170 insertions(+), 1243 deletions(-)

Series applied, thanks.


-- 
David Marchand