Re^7: Can you improve upon my algorithm.

Replies are listed 'Best First'.
Re^8: Can you improve upon my algorithm. by BrowserUk (Patriarch) on Mar 13, 2015 at 11:43 UTC
Be patient! I didn't say when :) FWIW: After killing the process I left running; I made one change and re-ran it: `my $nextRec = substr( $bufs[ $r ], -1024, 1024, '' ); // 1/64th itera +tions/buffer.` [download] And it completed in under 10 minutes: `E:\junk>c:t-salvaTheory.pl 0Took 492 seconds.` [download] With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked	[reply] [d/l] [select]
Re^9: Can you improve upon my algorithm. by salva (Canon) on Mar 13, 2015 at 23:28 UTC
Here we go! n-way-merge.c On my old home computer it merges at around 3GB/min, 100GB in half an hour. As it is just a prove of concept, it can only handle records formed by integers of type int64_t. The meaning of the constants are as follows: `N = maximum number of files that can be sorted CHUNKSIZE = the per-file memory buffer KEYSIZE = the number of int64_t numbers per record` [download] The source files are passed as arguments on the command line, the sorted output is sent to STDOUT. Only tested on Ubuntu 64bits. Update: It is difficult to count the number of instructions inside the loop on the hot path. It is certainly below 100, don't know if I have been able to reach the 50 I have predicted... I blame `gcc -O3` for that for unrolling small loops as the key comparison.	[reply] [d/l] [select]
Re^10: Can you improve upon my algorithm. by BrowserUk (Patriarch) on Mar 14, 2015 at 01:09 UTC
Case and analysis proven. Setting KEYSIZE = 1; compiling /Ox and running it against my 50x1GB files, it sustains a pretty steady 60MB in/60MB out per second, at a cpu utilisation of ~22-23%; which given my wc -c baseline test of 171mb/s is unidirectional, probably means that it is IO-bound rather than cpu-bound -- testimony to a well implemented heap. Total runtime for 50GB was a gnat's over 14 minutes which comes out at 61MB/s each way. Very impressive. Just makes you wonder about gnu/ms sort! I'll try and add the sort to split files into it tomorrow. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked	[reply]
Re^11: Can you improve upon my algorithm. by salva (Canon) on Mar 14, 2015 at 07:50 UTC
Re^12: Can you improve upon my algorithm. by BrowserUk (Patriarch) on Mar 14, 2015 at 14:14 UTC
Re^12: Can you improve upon my algorithm. by BrowserUk (Patriarch) on Mar 14, 2015 at 17:53 UTC


The stupid question is the question not asked
	PerlMonks