I'd like to perform a micro-benchmark, pitting ByteString comparision against Word comparison. What I'd like to do is: . Generate a bunch of random Word32s. . Generate strict ByteStrings containing those Word32s. . Compare every Word32 with every other Word32 for equality, and see how long it takes. . Ditto with ByteStrings. The first two are easy and I'm done with them already. The latter two seem like they'll run afoul of laziness. I have two ideas about how to do them: . Do every comparison with a list comprehension, compressing the result as I go using `all`. . Do every comparison in a recursive IO procedure. Are there other ways? Will strictness annotations, for example, allow me to run comparisons on larger lists? -- _jsn
Jason Dusek
. Compare every Word32 with every other Word32 for equality, and see how long it takes. . Ditto with ByteStrings.
The first two are easy and I'm done with them already. The latter two seem like they'll run afoul of laziness. I have two ideas about how to do them:
. Do every comparison with a list comprehension, compressing the result as I go using `all`. all is not a good idea: It stops as soon as it sees one false. Better count the number of equals. let count = length $ filter id [a==b,a <- bytestrings, b <- bytestrings]
. Do every comparison in a recursive IO procedure. Should work too. But you have to take care that implicit I/O thingies don't spoil one version of your timing tests.
Are there other ways? Will strictness annotations, for example, allow me to run comparisons on larger lists? Strictness annotation might help, but I don't think they are the correct tool to use here. The counting test I proposed above should run in O(1) stack and heap, as well as O(n^2) time, which is the best you can expect (of course, the list of bytestrings is O(n) on the heap).
Regards, Michael Karcher
participants (2)
-
Jason Dusek -
usenet＠mkarcher.dialup.fu-berlin.de