mpirvu
commented
4 years ago Statistics of small block sizes allocated by the persistent allocator at JITserver
Statistics on: Bytes requested per small alloc Num samples = 4360649 SUM=133188648.000000
MAX=863176.000000 MIN=8.000000 Mean=30.543309 StdDev=800.888920
--Bin-- --Value--
<8.000000 0.00% |
8.000000 0.05% |
16.000000 92.55% |*************************************
24.000000 2.07% |
32.000000 0.53% |
40.000000 0.31% |
48.000000 0.29% |
56.000000 1.26% |
64.000000 2.01% |
72.000000 0.00% |
80.000000 0.20% |
88.000000 0.00% |
96.000000 0.00% |
104.000000 0.00% |
112.000000 0.15% |
120.000000 0.00% |
128.000000 0.58% |The vast majority of allocations are 16 bytes in size. Having dedicated linked lists for sizes until 112 (inclusive) captures 99.42% of all allocations. Still 0.58% of 4360649 allocations (~25K) are large allocations that will be put onto a single linked list.
Experiments have shown that scalability of JITServer is affected by the implementation of the persistent allocator. The current implementation of the persistent allocator uses 12 linked lists of freed blocks: 11 of them for small fixed sized blocks (8, 16, 24,.. 88 bytes) and one of them for all larger blocks, sorted by size. When a client terminates, all its corresponding data structures (most of which are allocated with persistent memory) are freed, which creates huge linked lists of freed blocks. The problem is the list for larger blocks, because allocations and deallocations need to traverse it to find the appropriate spot for delete/add operations. Moreover, all allocations and deallocations are performed under a single which could be hold for long times while traversing this long linked list. Experiments have also shown that replacing our persistent allocator with a simple malloc makes the scalability issue to go away to a large extent.
There are a few possible solutions to alleviate this problem: 1) Use more dedicated lists for small, fixed size blocks. These lists are accessed fast because we always allocate/deallocate from/to head of the list. 2) Use a dedicated lock per linked list. This will accelerate the allocations for small blocks because they are not going to be held up by a big allocation which is expensive. 3) Use a balanced binary search tree instead of a list for the set of big lists.