en Copyright 2015 Java http://kernelsources.org:8080/source/history/linux/lib/region_alloc_benchmark.c#ae814200e8393fa504dd246e98fcba8f5493de28 Merge tag 'bitmap-for-7.3' of https://github.com/norov/linuxPull bitmap updates from Yury Norov: "The usual set of fixes, cleanups and performance improvements together with a couple of new tests: - bitmap_find_next_zero_area_off() optimization (Sunyi) - bitmap_find_next_zero_area_off(): return size when no zero area is found (Yury) - bitmap vs IDA vs Maple Tree performance test (Yury) - get rid of cpumap_print_to_pagebuf() (Yury) - use nr_node_ids in __nodemask_pr_numnodes() (Li RongQing) - bitops: make the *_bit_le functions use unsigned long (Benjamin) - bitmap scatter & gather test fix (Christophe) - use __ASSEMBLER__ in bitmap header files (Thomas)"* tag 'bitmap-for-7.3' of https://github.com/norov/linux: (25 commits) lib: test bitmap vs IDA vs Maple Tree performance for region allocations bitmap: Return size when no zero area is found media: s5p-mfc: Treat bitmap size as allocation failure crypto: ccp: Treat bitmap size as allocation failure powerpc/msi: Treat bitmap size as allocation failure ARM: dma-mapping: Treat bitmap size as allocation failure bitmap: drop bitmap_next_set_region() nodemask: reduce bitmap width to nr_node_ids in __nodemask_pr_numnodes() bitmap: Properly initialise destination bitmap for scatter & gather test lib/bitmap-str: get rid of cpumap_print_to_pagebuf() perf: Use sysfs_emit() for cpumask show callbacks PCI/sysfs: Use sysfs_emit() for cpumask show callbacks RDMA/hfi1: Use sysfs_emit() for cpumask show helper hwtracing: hisi_ptt: Use sysfs_emit() for cpumask show fpga: dfl-fme-perf: Use sysfs_emit() for cpumask show devfreq: Use sysfs_emit() for cpumask show callbacks cpu: Use sysfs_emit() for cpumask show callback x86/events: Use sysfs_emit() for cpumask show callbacks powerpc: Use sysfs_emit() for cpumask show callbacks arm: Use sysfs_emit() for cpumask show callbacks ... List of files: /linux/lib/region_alloc_benchmark.c Thu, 20 Aug 2026 20:41:46 +0200 Linus Torvalds <torvalds@linux-foundation.org> http://kernelsources.org:8080/source/history/linux/lib/region_alloc_benchmark.c#f4806cc63cc65bd752fd72d84937614dca6504ec lib: test bitmap vs IDA vs Maple Tree performance for region allocationsCompare the cost of allocating and freeing variable-sized regions usinga bitmap, IDA and a Maple Tree. All implementations process the samerandomly generated sequence of regions containing up to 32 entries, untilthe configured capacity is exhausted.The benchmark exercises monotonic allocation into an initially empty pool,followed by reverse-order freeing. It does not model fragmentation orinterleaved allocation and freeing, nor does it isolate locking or RCUoverhead. Allocation time includes the terminal failed request that detectsexhaustion.Run the benchmark at several capacities to show how the approaches scale.Report allocation and free times separately because bitmap, IDA and MapleTree removal have substantially different costs.On x86/kvm, the output example is:Start testing bitmap vs IDA vs Maple Tree region allocationmemory: bitmap is exact; IDA and Maple Tree are lower boundsType alloc (ns) free (ns) regions capacity memory (B)Bitmap 93457345 176151 60644 1000000 125000Maple 11758660 12870146 60644 1000000 1552656IDA 31066416 20870824 60644 1000000 134864Bitmap 919119 17679 6032 100000 12504Maple 1158193 1187140 6032 100000 154640IDA 2759670 2116004 6032 100000 14288Bitmap 17120 2043 613 10000 1256Maple 116350 117537 613 10000 15888IDA 243396 202654 613 10000 1872Bitmap 1220 262 55 1000 128Maple 12076 10106 55 1000 1552IDA 25730 20875 55 1000 144Bitmap 593 124 18 100 16Maple 3599 4782 18 100 528IDA 3266 1960 18 100 144Bitmap 414 129 10 10 8Maple 2143 1385 10 10 272IDA 892 648 10 10 16Region allocation benchmark completeReported IDA and Maple Tree memory figures exclude slab overheadand transient allocations. The Maple Tree figure is additionallya lower-bound estimate that assumes fully occupied leaf nodes andexcludes internal nodes.IDA has no region-allocation API, so each region is implemented asa sequence of single-ID allocations. The IDs remain contiguousbecause this benchmark fills an initially empty IDA monotonically.The benchmark is motivated by the discussion linked below about choosingthe best data structure for the channel ID pool with the capacity of 2048IDs for the nova GPU driver.Specifically for 2048 IDs the result is:Bitmap 5112 615 121 2048 256Maple 78526 59592 121 2048 3344IDA 165274 117761 121 2048 848The benchmark accepts a list of up to 64 nonzero capacities to test.For example: insmod region_alloc_benchmark.ko capacities=1024,2048,4096,65536The list may contain duplicate capacities. Each occurrence generates a newregion-size sequence, which is useful for collecting statisticalcharacteristics of the benchmark results.Link: https://lore.kernel.org/all/20260710-chid-maple-v1-1-4ee869055268@nvidia.com/Tested-by: Eliot Courtney <ecourtney@nvidia.com>Reviewed-by: Eliot Courtney <ecourtney@nvidia.com>Signed-off-by: Yury Norov <ynorov@nvidia.com> List of files: /linux/lib/region_alloc_benchmark.c Fri, 17 Jul 2026 07:32:40 +0200 Yury Norov <ynorov@nvidia.com>