diff options
author | Eelco Dolstra <eelco.dolstra@logicblox.com> | 2012-08-13 01:05:35 -0400 |
---|---|---|
committer | Eelco Dolstra <eelco.dolstra@logicblox.com> | 2012-08-13 01:05:35 -0400 |
commit | b9e5b908ed29bfb6cd82837f9f57293c1f63e999 (patch) | |
tree | bf83e68c67ec3e37720634c6ccca1d53594a3346 /src/libstore/misc.cc | |
parent | 4ccd48ce2478cbe1263605838969f89d5b745f0a (diff) |
Provide an efficient implementation of ‘elem’
The one in Nixpkgs is O(n^2), this one is O(n). Big reduction in the
number of list allocations.
Statistics before (on a NixOS system config):
time elapsed: 1.17982
size of a value: 24
environments allocated: 1543334 (39624560 bytes)
list elements: 9612638 (76901104 bytes)
list concatenations: 37434
values allocated: 1854933 (44518392 bytes)
attribute sets allocated: 392040
right-biased unions: 186334
values copied in right-biased unions: 591137
symbols in symbol table: 18272
number of thunks: 1392467
number of thunks avoided: 1507311
number of attr lookups: 430801
number of primop calls: 691600
number of function calls: 1492502
Statistics after:
time elapsed: 1.08683
size of a value: 24
environments allocated: 1384376 (35809568 bytes)
list elements: 6946783 (55574264 bytes)
list concatenations: 37434
values allocated: 1760440 (42250560 bytes)
attribute sets allocated: 392040
right-biased unions: 186334
values copied in right-biased unions: 591137
symbols in symbol table: 18273
number of thunks: 1297673
number of thunks avoided: 1380759
number of attr lookups: 430802
number of primop calls: 628912
number of function calls: 1333544
Diffstat (limited to 'src/libstore/misc.cc')
0 files changed, 0 insertions, 0 deletions