3 ms·

That does not explain it. Yes it will be slower with more buckets; how much? numbuckets uint64 uint32 1000 6 ms 5 ms 10000 6 ms 5 m

by pflanze 12y ago

That does not explain it. Yes it will be slower with more buckets; how much? numbuckets uint64 uint32 1000 6 ms 5 ms 10000 6 ms 5 ms 100000 6 ms 7 ms 1000000 14 ms 8 ms 10000000 38 ms 32 ms 20000000 38 ms 40000000 40 ms 80000000 44 ms 40 ms is still >50 times faster than the "software algorithm" in the video. And he didn't use 40 mio buckets there, as can be seen from the graphs. > make bins with different bounds You'd have to implement this and use a huge number of buckets and likely still use an older CPU than he did to get to his software timings. Or use a slow language implementation (interpreted or boxing arithmetic results). Or implement a slow algorithm like a linear search over the buckets (which would explain what the difference between his two algorithms of about a factor 2 is, the faster one stopping once the bucket is found). In any of these cases, he either doesn't know how to write fast code, or deliberately left the software version way slower than possible to have the FPGA version shine, pending any other better explanation.

pflanze 12y ago
I've now implemented the binary search version; I was right, the factor 10 was about correct, and even with 20 mio buckets the algorithm is still faster than the FPGA and more than 3 times faster than his faster software algorithm even though he's got a newer CPU (I'm running it on a Core 2 duo (single-threaded) at 2.5 Ghz), and again, he's really using something between about 1000..100000 buckets, which would make my program on my machine between 17 to 32 times faster than his: buckets gcc -O1 gcc -O3 1000 75 ms 72 ms 10000 105 ms 102 ms 100000 135 ms 136 ms 1000000 243 ms 240 ms 10000000 580 ms 20000000 693 ms (Results in my previous post were with gcc -O1.) All results so far were with random numbers with an uneven distribution: vec[i]= (i / len) * random_between(0.,1.). Here are the results for the binary search with vec[i]= random_between(0.,1.): buckets gcc -O1 1000 82 ms 10000 115 ms 100000 148 ms 1000000 360 ms 10000000 735 ms 20000000 860 ms (He's using a Gaussian distribution, not even.) Here's the code: int nvals= ..; double* vals= ..; int nbuckets= ..; double* buckets= ..; unsigned int* res= ..; int i; for (i=0; i<nvals; i++) { double val= vals[i]; int bi; { int lo=0, hi=nbuckets; while (lo < hi) { int mid= (lo+hi) / 2; if (val < buckets[mid]) { hi= mid; } else { lo= mid+1; } } bi= lo; } res[bi]++; } (Embedded within a Scheme driver program: http://christianjaeger.ch/scratch/binning.scm http://christianjaeger.ch/scratch/binning.scm)

by pflanze 12y ago

pflanze 12y ago

I've now implemented the binary search version; I was right, the factor 10 was about correct, and even with 20 mio buckets the algorithm is still faster than the FPGA and more than 3 times faster than his faster software algorithm even though he's got a newer CPU (I'm running it on a Core 2 duo (single-threaded) at 2.5 Ghz), and again, he's really using something between about 1000..100000 buckets, which would make my program on my machine between 17 to 32 times faster than his: buckets gcc -O1 gcc -O3 1000 75 ms 72 ms 10000 105 ms 102 ms 100000 135 ms 136 ms 1000000 243 ms 240 ms 10000000 580 ms 20000000 693 ms (Results in my previous post were with gcc -O1.) All results so far were with random numbers with an uneven distribution: vec[i]= (i / len) * random_between(0.,1.). Here are the results for the binary search with vec[i]= random_between(0.,1.): buckets gcc -O1 1000 82 ms 10000 115 ms 100000 148 ms 1000000 360 ms 10000000 735 ms 20000000 860 ms (He's using a Gaussian distribution, not even.) Here's the code: int nvals= ..; double* vals= ..; int nbuckets= ..; double* buckets= ..; unsigned int* res= ..; int i; for (i=0; i<nvals; i++) { double val= vals[i]; int bi; { int lo=0, hi=nbuckets; while (lo < hi) { int mid= (lo+hi) / 2; if (val < buckets[mid]) { hi= mid; } else { lo= mid+1; } } bi= lo; } res[bi]++; } (Embedded within a Scheme driver program: http://christianjaeger.ch/scratch/binning.scm http://christianjaeger.ch/scratch/binning.scm)