goerch / allocators.jl

Examples for the use of allocators in Julia

Allocators.jl

Rationale

Complex data structures with immutable nodes generate considerable memory pressure. Here we evaluate if custom allocation schemes can alleviate the problem.

Design

We provide 4 allocator classes Allocator, FreeListAllocator, SOAllocator and FreeListSOAllocator with a similar interface:

• getindex(alloc, i)
• setindex!(alloc, t, i)
• allocateend!(alloc)
• allocatebegin!(alloc)
• deallocateend!(alloc)
• deallocatebegin!(alloc)
• deallocate!(alloc, i])
• isempty(alloc)
• emptyend!
• emptybegin!

All allocators can be instantiated to be fixed size or resizable. FreeListAllocator, FreeListSOAllocator additionally keep an internal free list to reuse memory .SOAllocator and FreeListSOAllocator apply a simple SOA transform.

Tests

We test the allocators against basic data structures.

• List, see example/list.jl
• Stack, see example/stack.jl
• Queue, see example/queue.jl
• Set, see example/set.jl
• Dict see example/dict.jl

Results

Tested on Julia 1.6.3

Lists

100000 elements
 payload of 1 float(s)
  DataStructures.List                      29.633 ms (399492 allocations: 9.15 MiB)
  List without allocator                   599.500 μs (100001 allocations: 3.05 MiB)
  with fixed allocator                     288.900 μs (1 allocation: 16 bytes)
  with resizable allocator                 285.700 μs (1 allocation: 16 bytes)
  with fixed free list allocator           306.100 μs (1 allocation: 16 bytes)
  with resizable free list allocator       304.700 μs (1 allocation: 16 bytes)
  with fixed SOA allocator                 262.900 μs (1 allocation: 16 bytes)
  with resizable SOA allocator             282.900 μs (1 allocation: 16 bytes)
  with fixed free list SOA allocator       335.700 μs (1 allocation: 16 bytes)
  with resizable free list SOA allocator   357.800 μs (1 allocation: 16 bytes)
 payload of 10 float(s)
  DataStructures.List                      30.070 ms (399492 allocations: 15.25 MiB)
  List without allocator                   2.134 ms (100001 allocations: 10.68 MiB)
  with fixed allocator                     745.000 μs (1 allocation: 16 bytes)
  with resizable allocator                 684.900 μs (1 allocation: 16 bytes)
  with fixed free list allocator           925.400 μs (1 allocation: 16 bytes)
  with resizable free list allocator       880.100 μs (1 allocation: 16 bytes)
  with fixed SOA allocator                 494.900 μs (1 allocation: 16 bytes)
  with resizable SOA allocator             481.200 μs (1 allocation: 16 bytes)
  with fixed free list SOA allocator       957.800 μs (1 allocation: 16 bytes)
  with resizable free list SOA allocator   960.400 μs (1 allocation: 16 bytes)
 payload of 100 float(s)
  DataStructures.List                      65.440 ms (399492 allocations: 83.92 MiB)
  List without allocator                   24.405 ms (100001 allocations: 85.45 MiB)
  with fixed allocator                     7.327 ms (1 allocation: 16 bytes)
  with resizable allocator                 7.195 ms (1 allocation: 16 bytes)
  with fixed free list allocator           8.601 ms (1 allocation: 16 bytes)
  with resizable free list allocator       8.580 ms (1 allocation: 16 bytes)
  with fixed SOA allocator                 5.466 ms (1 allocation: 16 bytes)
  with resizable SOA allocator             5.437 ms (1 allocation: 16 bytes)
  with fixed free list SOA allocator       7.389 ms (1 allocation: 16 bytes)
  with resizable free list SOA allocator   7.522 ms (1 allocation: 16 bytes)
10 elements
 payload of 1 float(s)
  DataStructures.List                      3.013 μs (23 allocations: 680 bytes)
  List without allocator                   68.712 ns (11 allocations: 336 bytes)
  with fixed allocator                     33.837 ns (1 allocation: 16 bytes)
  with resizable allocator                 33.065 ns (1 allocation: 16 bytes)
  with fixed free list allocator           47.475 ns (1 allocation: 16 bytes)
  with resizable free list allocator       44.231 ns (1 allocation: 16 bytes)
  with fixed SOA allocator                 33.837 ns (1 allocation: 16 bytes)
  with resizable SOA allocator             36.959 ns (1 allocation: 16 bytes)
  with fixed free list SOA allocator       50.152 ns (1 allocation: 16 bytes)
  with resizable free list SOA allocator   51.833 ns (1 allocation: 16 bytes)
 payload of 10 float(s)
  DataStructures.List                      3.163 μs (23 allocations: 1.29 KiB)
  List without allocator                   147.619 ns (11 allocations: 1.11 KiB)
  with fixed allocator                     40.546 ns (1 allocation: 16 bytes)
  with resizable allocator                 46.970 ns (1 allocation: 16 bytes)
  with fixed free list allocator           79.062 ns (1 allocation: 16 bytes)
  with resizable free list allocator       82.952 ns (1 allocation: 16 bytes)
  with fixed SOA allocator                 40.344 ns (1 allocation: 16 bytes)
  with resizable SOA allocator             40.950 ns (1 allocation: 16 bytes)
  with fixed free list SOA allocator       82.073 ns (1 allocation: 16 bytes)
  with resizable free list SOA allocator   96.947 ns (1 allocation: 16 bytes)
 payload of 100 float(s)
  DataStructures.List                      5.171 μs (23 allocations: 8.32 KiB)
  List without allocator                   912.903 ns (11 allocations: 8.77 KiB)
  with fixed allocator                     181.081 ns (1 allocation: 16 bytes)
  with resizable allocator                 194.118 ns (1 allocation: 16 bytes)
  with fixed free list allocator           477.222 ns (1 allocation: 16 bytes)
  with resizable free list allocator       478.462 ns (1 allocation: 16 bytes)
  with fixed SOA allocator                 174.468 ns (1 allocation: 16 bytes)
  with resizable SOA allocator             176.623 ns (1 allocation: 16 bytes)
  with fixed free list SOA allocator       505.641 ns (1 allocation: 16 bytes)
  with resizable free list SOA allocator   477.949 ns (1 allocation: 16 bytes)

DataStructures.jl's list seems slightly broken. There is a performance gain depending on the payload when compared to the allocatorless implementation.

Stacks

100000 elements
 payload of 1 float(s)
  DataStructures.Stack             518.300 μs (198 allocations: 1.55 MiB)
  Stack with fixed allocator       221.700 μs (1 allocation: 16 bytes)
  Stack with resizable allocator   223.600 μs (1 allocation: 16 bytes)
 payload of 10 float(s)
  DataStructures.Stack             5.120 ms (296 allocations: 8.44 MiB)
  Stack with fixed allocator       462.000 μs (1 allocation: 16 bytes)
  Stack with resizable allocator   460.000 μs (1 allocation: 16 bytes)
 payload of 100 float(s)
  DataStructures.Stack             19.755 ms (296 allocations: 77.34 MiB)
  Stack with fixed allocator       5.377 ms (1 allocation: 16 bytes)
  Stack with resizable allocator   5.473 ms (1 allocation: 16 bytes)
10 elements
 payload of 1 float(s)
  DataStructures.Stack             842.857 ns (4 allocations: 16.25 KiB)
  Stack with fixed allocator       32.326 ns (1 allocation: 16 bytes)
  Stack with resizable allocator   34.778 ns (1 allocation: 16 bytes)
 payload of 10 float(s)
  DataStructures.Stack             2.400 μs (5 allocations: 88.20 KiB)
  Stack with fixed allocator       38.345 ns (1 allocation: 16 bytes)
  Stack with resizable allocator   46.512 ns (1 allocation: 16 bytes)
 payload of 100 float(s)
  DataStructures.Stack             4.200 μs (5 allocations: 808.20 KiB)
  Stack with fixed allocator       170.380 ns (1 allocation: 16 bytes)
  Stack with resizable allocator   158.540 ns (1 allocation: 16 bytes)

Comparison with DataStructures.jl's stack shows a performance gain depending on size of elements and size of the stack.

Queues

100000 elements
 payload of 1 float(s)
  DataStructures.Queue             452.100 μs (198 allocations: 1.55 MiB)
  Queue with fixed allocator       223.300 μs (1 allocation: 16 bytes)
  Queue with resizable allocator   243.700 μs (1 allocation: 16 bytes)
 payload of 10 float(s)
  DataStructures.Queue             5.008 ms (296 allocations: 8.44 MiB)
  Queue with fixed allocator       477.500 μs (1 allocation: 16 bytes)
  Queue with resizable allocator   918.700 μs (1 allocation: 16 bytes)
 payload of 100 float(s)
  DataStructures.Queue             18.375 ms (296 allocations: 77.34 MiB)
  Queue with fixed allocator       5.433 ms (1 allocation: 16 bytes)
  Queue with resizable allocator   6.161 ms (1 allocation: 16 bytes)
10 elements
 payload of 1 float(s)
  DataStructures.Queue             788.571 ns (4 allocations: 16.25 KiB)
  Queue with fixed allocator       31.319 ns (1 allocation: 16 bytes)
  Queue with resizable allocator   34.980 ns (1 allocation: 16 bytes)
 payload of 10 float(s)
  DataStructures.Queue             2.400 μs (5 allocations: 88.20 KiB)
  Queue with fixed allocator       35.520 ns (1 allocation: 16 bytes)
  Queue with resizable allocator   38.648 ns (1 allocation: 16 bytes)
 payload of 100 float(s)
  DataStructures.Queue             4.200 μs (5 allocations: 808.20 KiB)
  Queue with fixed allocator       155.907 ns (1 allocation: 16 bytes)
  Queue with resizable allocator   187.885 ns (1 allocation: 16 bytes)

Comparison with DataStructures.jl's queue shows a performance gain depending on size of elements and size of the queue.

Sets

100000 elements
  Set                                      14.487 ms (38 allocations: 7.50 MiB)
  DataStructures.SortedSet                 100.822 ms (91 allocations: 24.57 MiB)
  DataStructures.AVLTree                   4.112 s (7102520 allocations: 114.48 MiB)
  DataStructures.RBTree                    306.725 ms (200003 allocations: 12.21 MiB)
  DataStructures.SplayTree                 210.642 ms (200002 allocations: 9.16 MiB)
  AVLTrees.AVLSet                          24.511 ms (200002 allocations: 9.16 MiB)
  Tree without allocator                   30.209 ms (200003 allocations: 9.16 MiB)
  with fixed allocator                     50.160 ms (1 allocation: 16 bytes)
  with resizable allocator                 46.871 ms (1 allocation: 16 bytes)
  with fixed free list allocator           39.556 ms (1 allocation: 16 bytes)
  with resizable free list allocator       38.750 ms (1 allocation: 16 bytes)
  with fixed SOA allocator                 48.219 ms (1 allocation: 16 bytes)
  with resizable SOA allocator             50.328 ms (1 allocation: 16 bytes)
  with fixed free list SOA allocator       46.498 ms (1 allocation: 16 bytes)
  with resizable free list SOA allocator   45.623 ms (1 allocation: 16 bytes)
1000 elements
  Set                                      114.100 μs (18 allocations: 49.58 KiB)
  DataStructures.SortedSet                 344.400 μs (56 allocations: 322.94 KiB)
  DataStructures.AVLTree                   23.755 ms (28637 allocations: 509.97 KiB)
  DataStructures.RBTree                    3.016 ms (2003 allocations: 125.11 KiB)
  DataStructures.SplayTree                 1.934 ms (2002 allocations: 93.80 KiB)
  AVLTrees.AVLSet                          178.300 μs (2002 allocations: 93.78 KiB)
  Tree without allocator                   229.500 μs (2003 allocations: 93.80 KiB)
  with fixed allocator                     233.700 μs (1 allocation: 16 bytes)
  with resizable allocator                 235.100 μs (1 allocation: 16 bytes)
  with fixed free list allocator           237.000 μs (1 allocation: 16 bytes)
  with resizable free list allocator       236.700 μs (1 allocation: 16 bytes)
  with fixed SOA allocator                 207.000 μs (1 allocation: 16 bytes)
  with resizable SOA allocator             206.900 μs (1 allocation: 16 bytes)
  with fixed free list SOA allocator       239.400 μs (1 allocation: 16 bytes)
  with resizable free list SOA allocator   226.200 μs (1 allocation: 16 bytes)
10 elements
  Set                                      600.000 ns (8 allocations: 1.33 KiB)
  DataStructures.SortedSet                 2.156 μs (28 allocations: 5.75 KiB)
  DataStructures.AVLTree                   92.900 μs (102 allocations: 2.23 KiB)
  DataStructures.RBTree                    29.000 μs (23 allocations: 1.36 KiB)
  DataStructures.SplayTree                 17.600 μs (22 allocations: 1008 bytes)
  AVLTrees.AVLSet                          1.680 μs (22 allocations: 992 bytes)
  Tree without allocator                   1.090 μs (21 allocations: 976 bytes)
  with fixed allocator                     740.496 ns (1 allocation: 16 bytes)
  with resizable allocator                 739.344 ns (1 allocation: 16 bytes)
  with fixed free list allocator           775.701 ns (1 allocation: 16 bytes)
  with resizable free list allocator       783.146 ns (1 allocation: 16 bytes)
  with fixed SOA allocator                 900.000 ns (1 allocation: 16 bytes)
  with resizable SOA allocator             900.000 ns (1 allocation: 16 bytes)
  with fixed free list SOA allocator       983.333 ns (1 allocation: 16 bytes)
  with resizable free list SOA allocator   990.909 ns (1 allocation: 16 bytes)

DataStructures.jl's AVLTree seems slightly broken. Comparison with DataStructures.jl's RBTree shows some performance gain.

Dicts

100000 elements
 payload of 1 float(s)
  Dict                                     16.163 ms (43 allocations: 14.17 MiB)
  DataStructures.SortedDict                90.442 ms (89 allocations: 27.07 MiB)
  Tree without allocator                   31.310 ms (200003 allocations: 12.21 MiB)
  with fixed allocator                     62.263 ms (1 allocation: 16 bytes)
  with resizable allocator                 57.194 ms (1 allocation: 16 bytes)
  with fixed free list allocator           52.989 ms (1 allocation: 16 bytes)
  with resizable free list allocator       53.139 ms (1 allocation: 16 bytes)
  with fixed SOA allocator                 59.074 ms (1 allocation: 16 bytes)
  with resizable SOA allocator             49.803 ms (1 allocation: 16 bytes)
  with fixed free list SOA allocator       52.881 ms (1 allocation: 16 bytes)
  with resizable free list SOA allocator   48.492 ms (1 allocation: 16 bytes)
 payload of 10 float(s)
  Dict                                     42.391 ms (45 allocations: 74.17 MiB)
  DataStructures.SortedDict                96.470 ms (89 allocations: 45.07 MiB)
  Tree without allocator                   36.104 ms (200003 allocations: 24.41 MiB)
  with fixed allocator                     58.300 ms (1 allocation: 16 bytes)
  with resizable allocator                 63.216 ms (1 allocation: 16 bytes)
  with fixed free list allocator           52.756 ms (1 allocation: 16 bytes)
  with resizable free list allocator       53.264 ms (1 allocation: 16 bytes)
  with fixed SOA allocator                 55.434 ms (1 allocation: 16 bytes)
  with resizable SOA allocator             53.171 ms (1 allocation: 16 bytes)
  with fixed free list SOA allocator       53.637 ms (1 allocation: 16 bytes)
  with resizable free list SOA allocator   52.726 ms (1 allocation: 16 bytes)
 payload of 100 float(s)
  Dict                                     268.834 ms (46 allocations: 674.17 MiB)
  DataStructures.SortedDict                182.329 ms (89 allocations: 225.16 MiB)
  Tree without allocator                   117.662 ms (200003 allocations: 170.90 MiB)
  with fixed allocator                     127.329 ms (1 allocation: 16 bytes)
  with resizable allocator                 127.174 ms (1 allocation: 16 bytes)
  with fixed free list allocator           125.376 ms (1 allocation: 16 bytes)
  with resizable free list allocator       124.264 ms (1 allocation: 16 bytes)
  with fixed SOA allocator                 101.872 ms (1 allocation: 16 bytes)
  with resizable SOA allocator             102.102 ms (1 allocation: 16 bytes)
  with fixed free list SOA allocator       123.621 ms (1 allocation: 16 bytes)
  with resizable free list SOA allocator   112.293 ms (1 allocation: 16 bytes)
10 elements
 payload of 1 float(s)
  Dict                                     774.468 ns (8 allocations: 1.98 KiB)
  DataStructures.SortedDict                2.778 μs (26 allocations: 6.16 KiB)
  Tree without allocator                   1.370 μs (21 allocations: 1.27 KiB)
  with fixed allocator                     802.222 ns (1 allocation: 16 bytes)
  with resizable allocator                 783.333 ns (1 allocation: 16 bytes)
  with fixed free list allocator           828.169 ns (1 allocation: 16 bytes)
  with resizable free list allocator       970.833 ns (1 allocation: 16 bytes)
  with fixed SOA allocator                 858.621 ns (1 allocation: 16 bytes)
  with resizable SOA allocator             862.712 ns (1 allocation: 16 bytes)
  with fixed free list SOA allocator       963.636 ns (1 allocation: 16 bytes)
  with resizable free list SOA allocator   984.615 ns (1 allocation: 16 bytes)
 payload of 10 float(s)
  Dict                                     1.320 μs (8 allocations: 7.62 KiB)
  DataStructures.SortedDict                3.311 μs (26 allocations: 10.64 KiB)
  Tree without allocator                   1.420 μs (21 allocations: 2.52 KiB)
  with fixed allocator                     980.000 ns (1 allocation: 16 bytes)
  with resizable allocator                 934.483 ns (1 allocation: 16 bytes)
  with fixed free list allocator           1.010 μs (1 allocation: 16 bytes)
  with resizable free list allocator       1.010 μs (1 allocation: 16 bytes)
  with fixed SOA allocator                 1.000 μs (1 allocation: 16 bytes)
  with resizable SOA allocator             1.170 μs (1 allocation: 16 bytes)
  with fixed free list SOA allocator       1.230 μs (1 allocation: 16 bytes)
  with resizable free list SOA allocator   1.090 μs (1 allocation: 16 bytes)
 payload of 100 float(s)
  Dict                                     4.783 μs (9 allocations: 63.88 KiB)
  DataStructures.SortedDict                7.025 μs (26 allocations: 54.36 KiB)
  Tree without allocator                   2.833 μs (21 allocations: 17.52 KiB)
  with fixed allocator                     3.413 μs (1 allocation: 16 bytes)
  with resizable allocator                 3.425 μs (1 allocation: 16 bytes)
  with fixed free list allocator           3.550 μs (1 allocation: 16 bytes)
  with resizable free list allocator       3.625 μs (1 allocation: 16 bytes)
  with fixed SOA allocator                 2.711 μs (1 allocation: 16 bytes)
  with resizable SOA allocator             3.078 μs (1 allocation: 16 bytes)
  with fixed free list SOA allocator       2.689 μs (1 allocation: 16 bytes)
  with resizable free list SOA allocator   2.689 μs (1 allocation: 16 bytes)