(Tim: I don't know if/when I'll be able to blog about this, so feel free to
link to this message.)
Here are the results from my last full run (and actually only the 4th
successful one, since I ran into issues with fork() and the 32 bit address
space):
Language: OCaml
LoCs: 124 + ~20 (depends on how the code is partitioned into modules)
http://eigenclass.org/misc/wf2_multicore.ml
real 8m12.155s
user 137m24.981s
sys 19m52.597s
I have introduced a couple modifications since that could save one minute or
two (real time). Unfortunately, the machine has been pretty busy with
rwaldin's debugging and it's too late in my locale now, so this will remain
hypothetical for a while.
I have just learned about the canonical results at
/wf1/data/code/twbray/coolstack.log, and fortunately the output is identical,
as was the case in the first actual run. Not bad :)
The program is mostly I/O-bound, which is why the CPU time is not that large
compared to the wall-clock time. I haven't optimized I/O properly: the program
just uses a number of workers which perform line-oriented(!) I/O in separate
regions of the file. It still manages to read at >100MB/s, and the workers are
waiting for the data from disk half of the time.
I didn't use anything fancy to achieve concurrency this time, just good old
fork+pipe, wrapped in a neat "invoke" function (due to Jon Harrop) of type
('a -> 'b) -> 'a -> unit -> 'b
(For non-ML speakers: this is a function that takes a function, applies it to
the given argument in another process, and returns a function that will block
until the result is ready. You get parallelism by applying the "invoke"
function repeatedly, thereby launching several processes at once.)
I am pretty fond of the simple 7-line O(n * log(m)) function that keeps the
top m elements from a collection of n items (the original Ruby implementation
and most others are O(n * m * log(m)) or worse). Generating the reports for
the 42GB file takes 5s in my OCaml program, so it might take up to 1 minute in
most of the other solutions. The time will however remain nearly constant if
the top 100 or 1000 items are requested; the original Ruby solution could take
10 and 100 times longer (easily several minutes to a couple hours!) than with
10 elements.
--
Mauricio Fernandez - http://eigenclass.org
|
