![]() |
|
Don't ask to ask, just ask | |
PerlMonks |
Re^3: Why does Perl get slower when building a larger hash? (Not due to the memory swapping)by tmharish (Friar) |
on Mar 04, 2013 at 08:56 UTC ( [id://1021609]=note: print w/replies, xml ) | Need Help?? |
Dividing by $x ( number of files ) does not help cause you still have a O( log(N) ) in there ( the inner loop ) As a demonstration, consider the following code that benchmarks hash access times:
Output Benchmarked Hash access of size 1000 -> Access time for 1_000_000 keys: 0.11689305305481 Benchmarked Hash access of size 10000 -> Access time for 1_000_000 keys: 0.121062278747559 Benchmarked Hash access of size 100000 -> Access time for 1_000_000 keys: 0.125393152236938 Benchmarked Hash access of size 1000000 -> Access time for 1_000_000 keys: 0.116819381713867 Benchmarked Hash access of size 10000000 -> Access time for 1_000_000 keys: 0.118601083755493 Benchmarked Hash access of size 20000000 -> Access time for 1_000_000 keys: 0.117170572280884 You will notice that the time to access a million keys is nearly always the same - The memory on the other hand shoots up dramatically reaching 7.8 GB at around 25 Million entries ( which is why my bench-marking stops there ) Perl is working really hard in the background to ensure that it builds structures that can ensure that finding an element ( which should be O(N) ) is closing constant time here. UPDATE: Here is the output again with the CPU throttled so the difference can actually be seen: Benchmarked Hash access of size 1000 -> Access time for 1_000_000 keys: 0.438439846038818 Benchmarked Hash access of size 10000 -> Access time for 1_000_000 keys: 0.467595815658569 Benchmarked Hash access of size 100000 -> Access time for 1_000_000 keys: 0.615071773529053 Benchmarked Hash access of size 1000000 -> Access time for 1_000_000 keys: 0.804181814193726 Benchmarked Hash access of size 10000000 -> Access time for 1_000_000 keys: 0.873048782348633 Benchmarked Hash access of size 20000000 -> Access time for 1_000_000 keys: 0.910530567169189 So the time does go up - and thats expected. You cannot find an element in less than O( logN ); The speed here is because Perl optimizes this at a low level, but eventually the effect adds up.
In Section
Seekers of Perl Wisdom
|
|