[Bug binutils/11843] ld long link times due to compute_bucket_count() choosing hash table size

[todd dot veldhuizen at logicblox dot com]

------- Additional Comments From todd dot veldhuizen at logicblox dot com  
2010-07-28 22:09 -------
Here some tracing for compute_bucket_count() that illustrates the futility of
searching large numbers of hash table sizes.

Index: bfd/elflink.c
===================================================================
RCS file: /cvs/src/src/bfd/elflink.c,v
retrieving revision 1.372
diff -r1.372 elflink.c
31a32
> #include <sys/time.h>
5345a5347,5354
> 
> static double wallTime(void)
> {
>    struct timeval t;
>    gettimeofday(&t, 0);
>    return t.tv_sec + t.tv_usec/1000000.0;
> }
> 
5361a5371,5373
>   double startTime;
> 
>   startTime = wallTime();
5368a5381
>       long insert_count;
5377a5391,5392
>       insert_count=0;
> 
5419a5435,5436
>           insert_count += nsyms;
> 
5458a5476,5481
>               printf("elapsed=%7.4lfs size=%ld max=%lf (%lf%%) after %ld
inserts\n", 
>                  wallTime() - startTime,
>                  (long)i, 
>                  (double)max, ((double)max-best_chlen)/best_chlen*100.0, 
>                  insert_count);
>               insert_count=0;
5461a5485,5491
>           else if (insert_count > 1000000000L)
>           {
>             printf("elapsed=%7.4lfs No improvement after %ld inserts\n",
>                wallTime() - startTime,
>                insert_count);
>             insert_count=0;
>           }




Its output for the test case, on my machine, shows that after trying the first
three hash table sizes, no improvements of more than 1% occur, and after the
first 200 hash table sizes, no improvements whatsoever occur.

-bash-3.2$ ld -O1 many_symbols*.o -shared -o libxxx.so 
elapsed= 0.0045s size=99984 max=43186095512.000000 (-100.000000%) after 399936
inserts
elapsed= 0.0087s size=99985 max=34095909512.000000 (-21.048872%) after 399936
inserts
elapsed= 0.0129s size=99986 max=33926687032.000000 (-0.496313%) after 399936 
inserts
elapsed= 0.0170s size=99987 max=33836351808.000000 (-0.266266%) after 399936 
inserts
elapsed= 0.0586s size=99997 max=33830992776.000000 (-0.015838%) after 3999360
inserts
elapsed= 0.0628s size=99998 max=33828995144.000000 (-0.005905%) after 399936 
inserts
elapsed= 0.0836s size=100003 max=33823059872.000000 (-0.017545%) after 1999680
inserts
elapsed= 0.1293s size=100014 max=33802046320.000000 (-0.062128%) after 4399296
inserts
elapsed= 0.1625s size=100022 max=33791424296.000000 (-0.031424%) after 3199488
inserts
elapsed= 0.1833s size=100027 max=33740062104.000000 (-0.151998%) after 1999680
inserts
elapsed= 0.2167s size=100035 max=33725848184.000000 (-0.042128%) after 3199488
inserts
elapsed= 0.4254s size=100085 max=33716109728.000000 (-0.028875%) after 19996800
inserts
elapsed= 0.5258s size=100109 max=33682995136.000000 (-0.098216%) after 9598464
inserts
elapsed= 0.6515s size=100139 max=33669972112.000000 (-0.038663%) after 11998080
inserts
elapsed= 0.7270s size=100157 max=33644252600.000000 (-0.076387%) after 7198848
inserts
elapsed=11.1804s No improvement after 1000239936 inserts
elapsed=21.6568s No improvement after 1000239936 inserts
elapsed=32.1744s No improvement after 1000239936 inserts
elapsed=42.7346s No improvement after 1000239936 inserts
elapsed=53.3344s No improvement after 1000239936 inserts
elapsed=63.9556s No improvement after 1000239936 inserts
elapsed=74.6303s No improvement after 1000239936 inserts
elapsed=85.3426s No improvement after 1000239936 inserts
elapsed=96.0896s No improvement after 1000239936 inserts
elapsed=106.8647s No improvement after 1000239936 inserts
elapsed=117.6750s No improvement after 1000239936 inserts
elapsed=128.5248s No improvement after 1000239936 inserts
elapsed=139.4285s No improvement after 1000239936 inserts
elapsed=150.3337s No improvement after 1000239936 inserts
elapsed=161.2662s No improvement after 1000239936 inserts
elapsed=172.2233s No improvement after 1000239936 inserts
elapsed=183.2224s No improvement after 1000239936 inserts
elapsed=194.2606s No improvement after 1000239936 inserts
elapsed=205.3407s No improvement after 1000239936 inserts
elapsed=216.4314s No improvement after 1000239936 inserts
elapsed=227.5811s No improvement after 1000239936 inserts
elapsed=238.7598s No improvement after 1000239936 inserts
elapsed=249.9598s No improvement after 1000239936 inserts
etc.



-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=11843

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.