[RFC v2] Annotate malloc conditions with glibc_likely.

[OndÅej BÃlka <neleai at seznam dot cz>]

On Tue, Dec 10, 2013 at 09:54:31AM +0000, Will Newton wrote:
> On 9 December 2013 20:44, OndÅej BÃlka <neleai@seznam.cz> wrote:
> > Hi,
> >
> > Another little optimization in malloc is annotate that fastbins are
> > likely case. These should be fast path and given that other path
> > slower it should pay off.
> 
> In general I am not in favour of adding these types of annotations
> unless we can show they improve performance as they make code harder
> to read. They are also something of a blunt instrument - does "likely"
> mean will happen with 75% likelihood? 90%? 99%? I guess the results
> will vary with compiler and architecture as to whether or not the
> annotation helps or not.
> 
I wrote a test that I send, I added more annotations that make quite a
difference when fastbin is full.

When fastbin is empty half of time then branch mistprediction starts being
a problem which this benchmark catches and there is only small benefit.

That is problem of implementation for small requests a better way is
on empty condition allocate 8 chunks at once which also causes better
cache locality.

A results without and with attached patch are following.

old

 allocations in range 1-8:	118.689
 allocations in range 2-16:	116.139
 allocations in range 4-32:	122.606
 allocations in range 8-64:	135.817
 allocations in range 16-128:	160.102
 allocations in range 32-256:	229.255
 allocations in range 64-512:	281.434
 allocations in range 128-1024:	400
 allocations in range 256-2048:	621.67
 allocations in range 512-4096:	1104.91
 allocations in range 1024-8192:	2421.7
 allocations in range 2048-16384:	4834.78
 allocations in range 4096-32768:	9865.6
 allocations in range 1-8:	118.25
 allocations in range 2-16:	116.122
 allocations in range 4-32:	121.751
 allocations in range 8-64:	136.429
 allocations in range 16-128:	160.606
 allocations in range 32-256:	227.734
 allocations in range 64-512:	281.236
 allocations in range 128-1024:	394.561
 allocations in range 256-2048:	609.688
 allocations in range 512-4096:	1082.73
 allocations in range 1024-8192:	2296.92
 allocations in range 2048-16384:	4722.11
 allocations in range 4096-32768:	9748.97
 allocations in range 1-8:	118.287
 allocations in range 2-16:	116.089
 allocations in range 4-32:	121.822
 allocations in range 8-64:	136.193
 allocations in range 16-128:	160.722
 allocations in range 32-256:	227.183
 allocations in range 64-512:	280.237
 allocations in range 128-1024:	393.878
 allocations in range 256-2048:	607.415
 allocations in range 512-4096:	1079.1
 allocations in range 1024-8192:	2269.06
 allocations in range 2048-16384:	4698.77
 allocations in range 4096-32768:	9709.76
 allocations in range 1-8:	118.371
 allocations in range 2-16:	116.09
 allocations in range 4-32:	121.652
 allocations in range 8-64:	136.227
 allocations in range 16-128:	160.741
 allocations in range 32-256:	227.857
 allocations in range 64-512:	280.756
 allocations in range 128-1024:	394.021
 allocations in range 256-2048:	609.028
 allocations in range 512-4096:	1077.23
 allocations in range 1024-8192:	2270.23
 allocations in range 2048-16384:	4698.65
 allocations in range 4096-32768:	9708.73
 allocations in range 1-8:	118.061
 allocations in range 2-16:	116.27
 allocations in range 4-32:	121.893
 allocations in range 8-64:	136.55
 allocations in range 16-128:	160.553
 allocations in range 32-256:	227.641
 allocations in range 64-512:	280.883
 allocations in range 128-1024:	394.121
 allocations in range 256-2048:	607.112
 allocations in range 512-4096:	1079.12
 allocations in range 1024-8192:	2267.24
 allocations in range 2048-16384:	4700.08
 allocations in range 4096-32768:	9709.41

new

 allocations in range 1-8:	107.242
 allocations in range 2-16:	104.76
 allocations in range 4-32:	115.903
 allocations in range 8-64:	129.071
 allocations in range 16-128:	157.852
 allocations in range 32-256:	228.652
 allocations in range 64-512:	280.58
 allocations in range 128-1024:	406.251
 allocations in range 256-2048:	638.335
 allocations in range 512-4096:	1128.08
 allocations in range 1024-8192:	2337.02
 allocations in range 2048-16384:	4810.68
 allocations in range 4096-32768:	9824.05
 allocations in range 1-8:	106.484
 allocations in range 2-16:	105.134
 allocations in range 4-32:	113.38
 allocations in range 8-64:	129.916
 allocations in range 16-128:	158.132
 allocations in range 32-256:	226.758
 allocations in range 64-512:	280.586
 allocations in range 128-1024:	400.147
 allocations in range 256-2048:	627.112
 allocations in range 512-4096:	1096.87
 allocations in range 1024-8192:	2278.98
 allocations in range 2048-16384:	4695.18
 allocations in range 4096-32768:	9722.37
 allocations in range 1-8:	106.837
 allocations in range 2-16:	104.966
 allocations in range 4-32:	114.843
 allocations in range 8-64:	138.233
 allocations in range 16-128:	162.073
 allocations in range 32-256:	227.041
 allocations in range 64-512:	297.998
 allocations in range 128-1024:	408.122
 allocations in range 256-2048:	645.366
 allocations in range 512-4096:	1130.57
 allocations in range 1024-8192:	2326.98
 allocations in range 2048-16384:	4824.57
 allocations in range 4096-32768:	9800.23
 allocations in range 1-8:	106.691
 allocations in range 2-16:	105.315
 allocations in range 4-32:	113.97
 allocations in range 8-64:	130.445
 allocations in range 16-128:	156.499
 allocations in range 32-256:	226.695
 allocations in range 64-512:	280.039
 allocations in range 128-1024:	400.835
 allocations in range 256-2048:	625.75
 allocations in range 512-4096:	1093.93
 allocations in range 1024-8192:	2280.61
 allocations in range 2048-16384:	4695.94
 allocations in range 4096-32768:	9677.53
 allocations in range 1-8:	106.672
 allocations in range 2-16:	105.131
 allocations in range 4-32:	113.929
 allocations in range 8-64:	130.109
 allocations in range 16-128:	157.513
 allocations in range 32-256:	226.601
 allocations in range 64-512:	280.75
 allocations in range 128-1024:	400.561
 allocations in range 256-2048:	627.846
 allocations in range 512-4096:	1095.34
 allocations in range 1024-8192:	2280.27
 allocations in range 2048-16384:	4693.53
 allocations in range 4096-32768:	9678.55

Attachment: 0002-anotate.patch
Description: Text document