memory: reduce large allocations for small pools
memory: reduce large allocations for small pools

Small pools provide small objects by allocating large spans and
dividing them.  Those spans, however, are too generous, resulting in
waste if only a small number of objects are allocated, and in vulnerability
to fragmentation as the largest span is half a megabyte in size.

This patch changes the search for the optimal span size to no longer
require a power-of-two span size, and to reduce the minimum number of
objects per span from 32 to 4 (reducing amortization somewhat). The largest
span size is now 64kB.

Before:

objsz spansz    usedobj       memory  wst%
    1   4096          0            0   0.0
    1   4096          0            0   0.0
    1   4096          0            0   0.0
    1   4096          0            0   0.0
    2   4096          0            0   0.0
    2   4096          0            0   0.0
    3   4096          0            0   0.0
    3   4096          0            0   0.0
    4   4096          0            0   0.0
    5   4096          0            0   0.0
    6   4096          0            0   0.0
    7   4096          0            0   0.0
    8   4096      12299       106496   7.6
   10   4096       1738        24576  29.1
   12   4096        171         8192  74.9
   14   4096          0         8192  99.8
   16   4096       1726        32768  15.7
   20   4096       1692        36864   7.8
   24   4096       2718        69632   5.9
   28   4096       1286        40960  11.9
   32   4096       2959       102400   7.5
   40   4096       2779       118784   6.0
   48   4096       1505        77824   6.8
   56   4096       3631       208896   2.5
   64   4096       6814       442368   1.4
   80   4096       3374       274432   1.3
   96   4096       1480       151552   4.7
  112   4096        543        69632  11.1
  128   4096        580        86016  13.7
  160   8192       1619       270336   3.8
  192   8192        525       114688  10.5
  224   8192        280        81920  21.9
  256   8192        203        73728  29.5
  320  16384        364       147456  20.6
  384  16384         92        65536  44.5
  448  16384        178       114688  28.9
  512  16384     328826    168394752   0.0
  640  32768         59        98304  61.2
  768  32768        260       262144  22.3
  896  32768         49        98304  53.8
 1024  32768         55        98304  42.7
 1280  65536        145       262144  28.8
 1536  65536         79       262144  52.1
 1792  65536        204       524288  28.7
 2048  65536         67       196608  30.2
 2560 131072          9       262144  90.8
 3072 131072         74       262144  11.7
 3584 131072         32       393216  69.3
 4096 131072         32       393216  66.7
 5120 262144          8       524288  91.8
 6144 262144         77      1048576  53.3
 7168 262144         45       786432  57.4
 8192 262144        116      1572864  39.6
10240 524288         35      1048576  65.4
12288 524288          8      1048576  89.1
14336 524288         34      1572864  67.4
16384 524288         97      3145728  49.5

After:

Small pools:
objsz spansz    usedobj       memory  wst%
    1   4096          0            0   0.0
    1   4096          0            0   0.0
    1   4096          0            0   0.0
    1   4096          0            0   0.0
    2   4096          0            0   0.0
    2   4096          0            0   0.0
    3   4096          0            0   0.0
    3   4096          0            0   0.0
    4   4096          0            0   0.0
    5   4096          0            0   0.0
    6   4096          0            0   0.0
    7   4096          0            0   0.0
    8   4096        171         8192  83.3
   10   4096          1         8192  99.7
   12   4096        171         8192  74.9
   14   4096          0         8192  99.8
   16   4096       1632        32768  20.3
   20   4096       1248        32768  23.4
   24   4096       2263        61440  11.2
   28   4096        789        28672  22.8
   32   4096       2375        81920   7.2
   40   4096       2598       110592   5.6
   48   4096       1083        57344   9.0
   56   4096       2450       143360   4.1
   64   4096       5886       380928   1.1
   80   4096       2680       221184   2.7
   96   4096        945        98304   6.2
  112   4096        246        36864  23.7
  128   4096        367        57344  18.1
  160   4096       1396       229376   0.3
  192   4096        354        81920  15.5
  224   4096        108        40960  39.4
  256   4096         97        45056  44.9
  320   8192        147        73728  33.9
  384   8192         74        32768  11.7
  448   4096         40        36864  49.8
  512   4096     327335    167624704   0.0
  640  12288         59        49152  22.1
  768  12288        229       245760  28.4
  896   8192         20        73728  74.1
 1024   4096         49        77824  35.5
 1280  20480        115       204800  28.1
 1536  12288         90       245760  43.8
 1792  16384          9       147456  87.5
 2048   8192         67       155648  11.8
 2560  20480          8       204800  90.0
 3072  12288         71       466944  53.3
 3584  28672          1       286720  98.8
 4096  16384         32       311296  57.9
 5120  20480          8       389120  89.5
 6144  24576         29       466944  61.8
 7168  28672         12       544768  84.2
 8192  32768         66       622592  13.2
10240  40960          2       778240  97.4
12288  49152          6       933888  92.1
14336  57344          2      1089536  97.4
16384  65536          2      1245184  97.4

Message-Id: <a441196226fb59088a20527239f2d2780c0819e8@scylladb.com>

cloudius-systems/seastar,dreamsxin/seastar,dreamsxin/seastar,scylladb/seastar,scylladb/seastar,dreamsxin/seastar,cloudius-systems/seastar,scylladb/seastar,syuu1228/seastar,avikivity/seastar,cloudius-systems/seastar,avikivity/seastar,syuu1228/seastar,avikivity/seastar,syuu1228/seastar