[erlang-questions] Strange optimization result

[Steve Vinoski]

On 10/20/07, Anders Nygren <anders.nygren@REDACTED> wrote:
>
> Hi
> I am playing around with Tim Bray's widefinder problem.
> Actually I am playing with Steve V's latest version
> see http://steve.vinoski.net/blog/2007/10/18/ok-just-one-more-wf/
>
> In it he is using a dict for Boyer-Moore searching, the dict is just
> a map from char code to shift amount i.e. the keys are 1 - 255
> and the values are ints.
> I figured that it would be faster to just have a tuple with the shift
> values.
> So I changed the code to generate a tuple instead of a dict. And the
> lookups changed from
> dict:fetch(C1, Tbl)
> to
> element(C1,Tbl)
>
> To my big surprise the program now runs slower.
> On a file with 1M rows approx. 192 M.
>
> Steve's original code, using dics, as reported by time
> real    0m20.444s
> user    0m37.718s
> sys     0m0.612s
>
> My modified, using a tuple
> real    0m25.849s
> user    0m44.203s
> sys     0m3.332s
>
> Interesting to note is the high value for sys in my version.
> Also the tuple version does not manage to max out the CPU use
> it peaks at ~85%, while the dict version gets 100% CPU load.
> The program starts 64 erlang processes on my dual core laptop.
>
> My only idea is that this is caused by some pathological CPU cache
> behaviour. Does anyone have a better explanation?
>

Hi Anders, I don't know the answer, but I agree that it seems strange. I
wrote some tests that did simple lookups against dicts and tuples in a loop
and timed them, and tuples were faster, but when I used them in my Wide
Finder code, they were slower, just as you saw.

--steve
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20071021/9f6a1791/attachment.htm>