User talk:WillNess: Difference between revisions
→Space complexity improvement -- Hamming numbers: something strange
(→Space complexity improvement -- Hamming numbers: something strange) |
|||
Line 76:
::::::: I've tried it locally, and it reports "234MB memory in use" for 1B and 1187MB for the 10B. I don't understand what is this 7.8MB figure that Ideone shows for both. I was misled by this. -- [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 10:45, 22 August 2016 (UTC)
::::::: BTW the really short version of it is just <code>(Sum c,b) = mconcat [ ( Sum (i+1), ...</code>. Here it could be argued that it '''''ought''''' to be compiled efficiently, as the whole premise of Monoids is that associativity enables re-parenthesization ''(<code>a:b:c:... = [a]++([b]++([c]++...)) = ([a]++[b])++([c]++...)</code>)'', which is the basis for the efficiency of the strict left fold. Yet it is more than twice worse than the <code>prod</code> code, both in time and space.
::::::: Something strange is going on with this at Ideone. I've always assumed that the memory usage reported by Ideone follows the ''"total memory in use"'' reported by <code>+RTS -s</code>, with some constant overhead. It looks '''''as if''''' some optimization kicks in for the lower ''n''s, and the near-zero memory operation ''is'' being achieved there <sup>(*)</sup>; and for the larger values this optimization does not kick in and the execution reverts to what we both seen locally, i.e. the growing memory usage. BTW, I got 1B:0.45s-269MB and 10B:1.75s-1343MB, which suggests 1T:38s-'''28.8GB''' ''"total memory in use"''. The fold-based version indeed did good at 1T:11.2s-'''10MB'''. I use the signature <code>Int -> (Double, (Int,Int,Int))</code> which produced the fastest code in my tests (simple -O2).
::::::: --- <sup>(*)</sup> this is also supported by the '''very fast execution times for the 10B <code>prod</code>-based version'''. Usually Ideone is about 3.5x slower than my box, but this ran 1.25x '''faster''' (!!??). But, comparing it with the 10B timing for the local '''<code>foldl'</code>-based version''', it indeed ran 3.85x slower. -- [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 17:05, 22 August 2016 (UTC)
| |||