holy frijoles: constant factors matter.
john at repetae.net
Wed Oct 12 22:22:07 EDT 2005
these differences in jhc runtimes were the result of a single line change.
< total time = 44.32 secs (2216 ticks @ 20 ms)
< total alloc = 9,372,965,276 bytes (excludes profiling overheads)
> total time = 36.74 secs (1837 ticks @ 20 ms)
> total alloc = 6,621,233,076 bytes (excludes profiling overheads)
the odd thing is, the change should not have changed the order of the
algorithm at all. the change was (effectivly)
Map.fromAscList . map f . Map.toAscList
being changed to
both are O(n). but those constant factors matter. a lot.
in any case, the reason I mention it is because if there were routines
for converting between Set and Map that preserved the binary tree
structure, I think their use could dramatically speed up many routines.
In jhc (and other programs), I convert between them all the time and I'd
hate to have to fall back on type Set a = Map a ().
Map already has a keysSet, but it does the same inefficient thing
building an intermediate list. all that is needed is a
setToMap :: (a -> b) -> Set a -> Map a b
the keysSet could be made more efficient in the next point release, but
I guess adding setToMap would have to wait til the next major one.
John Meacham - ⑆repetae.net⑆john⑈
More information about the Libraries