My current Perl Projects - Benchmarks |
These benchmark pages are now outdated. See here for up-to-date benchmarks (see also Bigbench, which is used to generate them). 2002-01-09
The math inside Math::String is done via Math::BigInt, and thus only a a faster Math::BigInt would help us. The only other operations that take time in Math::String are new() and bstr(). Therefore we are concerned to get them as fast as possible.
The old Math::String version (prior 2001-02-14) suffered from the fact that it would need to construct a charset for each Math::String object. Although this time is negletible in contrast to the time needed to convert between string/number, the introduction of Math::String::Charset forced me to look at the code, and I improved it a great deal. The caching of certain things inside the charset helps a lot, too.
The new benchmarks regarding overloading of '+=' and the early out for the add() are below.
The brand-new benchmarks regarding overloading bool are at the bottom.
The images were created by gnuplot. If you are interested in the benchmark script, mail me.
new() |
As you can see, new() is linear in time ( O(N) where N is number of characters in string, but we expected this all along) , and now about 20% faster. Strings of length 0 and 1 are now special cases and even MUCH faster ;).
X-axis is string-length, y-axis time taken for one operation.
bstr() |
bstr() is also linear in time. The new code is much faster, too. (What you don't see due to scaling is that it is significantly faster for strings of length 0 ;) The humps stem probably from the fact that the underlying BigInt code uses a granularity of 100.000, and passwords of different length give different increase in numbers. This means that not every increase in string length has an equal effect on the time taken.
X-axis is string-length, y-axis time taken for one operation.
++, bstr() |
A Math::String $x++, followed by a $x->bstr() (or "$x") is an expensive way of the Perl build-in ++ operator. Well, if your character set is different from 'a'..'z', you are stuck with Math::String, but it would be nice to know how costly it really is.
Well, the bad news: build-in ++ is about 10.000 faster :-/ That is why in the next image the blue line is really close to 0.
X-axis is string-length, y-axis time taken for one operation.
I do not know why there is this big hump for 19,20 and 21 character long strings. I do not see anything special about these lengths and why the bstr() operation is 3 times slower for them. But this happens everytime I choose a character set of length 26, and I am determined to find out what happens. Perhaps a bug in Math::BigInt?
Math::BigInt: $x += $y; and $x = $x + $y |
The overloading of '+=' saves a copy per operation, and if both number are large and roughly the same size, this copy takes about 20-30% of the time.
Both images accidentily say Math::String in the title, but I tested Math::BigInt. OTOH, Math::String is simple a overhead of one call to Math::BigInt for math operations, so the images are not that wrong.
X-axis is number of digits, y-axis time taken for one operation.
Due to the new early out in add, $x += $y for small $y is now a constant operation, whereas before it took a time proportional to the length of $x.
X-axis is number of digits, y-axis time taken for one operation.
Math::BigInt: bool respective if($x) |
The overloading of bool can use $x->is_zero() instead of stringify the number. The latter is not a constant operation, but depends on the length of the number. As you can see, things like if ($x) are now O(1) (and a lot faster, too):
X-axis is number of digits, y-axis time taken for one operation.
Here is a comparisation between original Math::BigInt, my new v1.15 and the brand-new v1.16:
As you can see, the original code used an algorithm, that was much faster, but equals O(N). Strangely, the crossover does not happen at about 220 digits, instead the time for one operation drops sharply, only to raise very slowly. The real crossover (where the new algorithm is faster) is at about 1500 digits. I think the drop is because Perl tries to convert the BigInt into a number, and any string over a certain lenght is not converted, but evaluated as string instead (original code used numify instead of bool).
X-axis is number of digits, y-axis time taken for one operation.