I don't think there would be much point, hah - JS will definitely be slower than optimized C. It's the crowdsourcing aspect that gives us a chance - it is very easy for anyone to just pull up the web page.
For unrelated reasons I recently did some benchmarking of SHA-1 in JavaScript vs Java. That particular benchmark was about 20x slower in the browser (both Chrome and Firefox 3.5) than on the JVM.
It's going to be a lot slower, particularly with the goal of not slowing down a person's browser. By default, at least for me, their page is doing 1 hash per 200ms, or 5/second.
On the other hand, a quick Haskell implementation using Data.Digest.Pure.SHA is doing about 6,000 hashes per second (might have been 8000, I forget now) per core on an Intel(R) Core(TM)2 Duo CPU E6750 @ 2.66GHz
So you're looking at 1000 people to equal one core of a decent desktop. It's certainly an interesting approach, and has a lot of potential. I'm just not sure the marketing is there with the "help us win" motivation.
This JavaScript version: http://news.ycombinator.com/item?id=715014 (which doesn't do any throttling) is doing ~1500 hashes per second in one Chrome tab on my fairly old (2.8 GHz Pentium D) desktop. I'm curious how fast it would be on your Core 2 Duo in two Chrome tabs.
I think GPU's are going to win this "Yeah, my 5 GPUs are currently cranking at a total rate of 800 M/sec" they are are already looking at the low 30's.
This idea is a really well thought and implemented. This may be a new way of cloud sourcing. Have you considered making a facebook app? It would definitely attract many more people than this. Of course you shou ld offer some carrots for users that do not have any idea what's going on.
oops :) I intended to comment on racymorgan implementation not this one. But this is good too. Opening tabs sometimes cause these mistakes. Sorry for both parties.
It's pretty well though out and is awesome in principle. The problem is that our interpreted javascript cloud network is getting owned by the awesome power of nVidia GPUs.
"Yeah, my 5 GPUs are currently cranking at a total rate of 800 M/sec. (Best score of 39 after running for a few minutes.)
(Hah! Just got lucky and hit 35 on one card after an hour.) "
- The nVidia CUDA group
I hope you aren't disappointed when you a see a new update on your AJAX postback page that looks like a new winning string, when you see it is simply a note from me. :)
(I also generated a few hundred thousand hashes for you)
a quicker approach to your bit counting routines:
(in C because that's what I'm most comfortable with, but it is pretty much a drop-in replacement for your code)
#include <stdio.h>
char dist[256];
hamm_init()
{
int i,j,n;
for (i=0;i<256;i++) {
j = i;
n = 0;
while (j) {
if (j & 1) {
n++;
}
j >>= 1;
}
dist[i] = n;
}
}
int hamming_distance(char * hash1,char * hash2) {
//calculate the distance between two hashes
int d = 0;
while (*hash1) {
if (*hash2 == 0) {
break;
}
d += dist[*hash1++ ^ *hash2++];
}
return d;
}
main()
{
hamm_init();
printf("0 %d\n",hamming_distance("abcd","abcd"));
printf("1 %d\n",hamming_distance("accd","abcd"));
}
Yeah, my JS hamming distance implementation is pretty miserable. I'm no bit wizard, but I thikn I can modify the SHA1 function (before it returns the value as a hex string) and XOR the 5 vars with the hex value that they gave us, and then count the set bits. Couldn't get it working last night though so I switched over to this
You might also consider removing UTF8Encoding from SHA1 implementation, I might be wrong, but I think contest states no encoding should be used - i.e. ASCII only. If that's a care, that's a useless O(N) operation.
I would be interested to see if you could get something like this running using the Google NACL project (http://code.google.com/p/nativeclient/). Wouldn't that give you then benefit of having native code running on any machine that went to the page and had the plugin installed? You could have the user install a plugin when they went to the page and then reload the page. Just popped into my head, probably too late to implement anything now, but might be fun to give it a go.
As a CPU contributor, I demand that you give us stats as to which browsers were the fastest for your computation! This could be an interesting comparison point for the bundled javascript engines. (Maybe :))
chrome definitley wins. but i think, (tracemonkeys) tracing could be THE feature in this case. lots of unrolled loops ... hopefully mozilla gets more out of it over time.
Also, are you logging IP's for your best results? Would be cool to know if my machine was the one that came up with the shortest hamming distance (obviously IP's aren't a guaranteed way to figure this out, but still...)
To get more people excited, might be a good idea to say how many cycles each browser has contributed - make it a fight of Chrome vs Firefox vs Safari ;)
As far as I can tell, the browsers only contact him if they find a string with a shorter hamming distance, otherwise it's entirely offline, including picking random words.
Eh, I'll leave it on my PowerMac overnight. Just fyi, I've donated the following browsers...
OS X:
Safari,
Firefox 3.5,
Webkit Nightly,
Chromium Nightly,
Opera 10 beta 2,
Shiira,
Camino 2,
Seamonkey,
Sunrise,
Flock
Then I have 3 virtual machines open...
Windows XP #1:
Firefox 3.5,
Chrome,
Internet Explorer 6 (Dev testing bed, not upgrading, but take it anyway),
Opera 9,
Maxthon 2 (Surprised I even had it)
Windows XP #2:
Firefox 3.5,
Chrome,
Internet Explorer 7,
Opera 9,
Maxthon 2
Windows XP #3:
Firefox 3.5,
Chrome,
Internet Explorer 8,
Opera 9,
Maxthon
I'd donate an Ubuntu VM or two, but... they don't wanna start up at this point. shrug
This may not help, I dunno, but I'm certainly not using the computer. Have a blast, and good luck!
Let's keep some perspective here folks. The idea is cool and all, but as discussed in the other thread, SHA-1 throughput on GPUs is between 200 million and 600 million per second, depending on the GPU (http://forums.nvidia.com/index.php?s=&showtopic=102349&#...). On the other hand, the maximum throughput that people are getting with JS is about 3000/second. Which is a hundred thousand times slower.
I think it is safe to conclude that browser-based crowdsourcing is not a compelling approach to numerical computation.
That's true and it was my first thought (which is why I asked about benchmarking the js code). What it did do was to get a pretty clever idea out into the world, which is to crowdsource the answer to some contest.
Contests are usually held to fire up peoples creativity and this idea to solve it via the browser as an ad-hoc cluster is really pretty creative.
Personally I think to try to solve this contest by brute forcing it is changing it in to a simple pissing contest between the various hardware / software combination, I'm sure some guy with an fpga kit will do a lot better than the CUDA competitors.
It would be nicer if someone discovered a previously undetected flaw and solved the contest through a backdoor. that would be hacker news :)
If Engine Yard was trying to promote their cloud services with this contest it's rather ironic it appears it will probably be won be a few desktop computers with high end GPUs, which cloud hosts usually don't even have.
Would you be willing to write up the stats of your experiment once the challenge is over? I'd be really interested to know how much compute power you were able to harvest and what was the rate of compute acquisition.
Terrific idea and implementation. I have 10 tabs on Chrome.
Good luck.
As far as I can tell, the browsers only contact him if they find a string with a shorter hamming distance, otherwise it's entirely offline, including picking random words.
76 comments
[ 3.0 ms ] story [ 138 ms ] threadgood luck!
On the other hand, a quick Haskell implementation using Data.Digest.Pure.SHA is doing about 6,000 hashes per second (might have been 8000, I forget now) per core on an Intel(R) Core(TM)2 Duo CPU E6750 @ 2.66GHz
So you're looking at 1000 people to equal one core of a decent desktop. It's certainly an interesting approach, and has a lot of potential. I'm just not sure the marketing is there with the "help us win" motivation.
I upvoted you :).
Good luck.
"Yeah, my 5 GPUs are currently cranking at a total rate of 800 M/sec. (Best score of 39 after running for a few minutes.)
(Hah! Just got lucky and hit 35 on one card after an hour.) " - The nVidia CUDA group
(I also generated a few hundred thousand hashes for you)
Edit: it's back up to 43, a nice improvement from 48 from a few minutes ago.
I added a word checker, so no more of this tomfoolery!
"Oh but for your trouble I generated a few hundred thousand hashes for you. --Phil Freo"
Thanks Phil :-) Your message's hash had a hamming distance of 73
Now, I opened it also in Safari and says: The smallest Hamming distance we've achieved so far is: 0
0? Does that mean you got one?
Edit: Ok. Solved.
Edit: fixed and fixed
You might also consider lookup tables for Hamming distance (google for "counting bits").
Unless you're using characters > 255, UTF-8 is identical to ASCII.
http://en.wikipedia.org/wiki/UTF-8
Hm, on second thought UTF8(ASCII) is -always- == ASCII, since ASCII is only defined for 0-127, unless you count the extended variants :P
http://en.wikipedia.org/wiki/ASCII
As far as I can tell, the browsers only contact him if they find a string with a shorter hamming distance, otherwise it's entirely offline, including picking random words.
(I second, or third, the browser-war idea.)
I wouldn't leave it running if you killed my processor.
But you made it painless, so you get at least a few hours of runtime on me @ 1ms.
http://twitter.com/rikfaith/statuses/2743945177
I have no way to check. True or not?
OS X: Safari, Firefox 3.5, Webkit Nightly, Chromium Nightly, Opera 10 beta 2, Shiira, Camino 2, Seamonkey, Sunrise, Flock
Then I have 3 virtual machines open...
Windows XP #1: Firefox 3.5, Chrome, Internet Explorer 6 (Dev testing bed, not upgrading, but take it anyway), Opera 9, Maxthon 2 (Surprised I even had it)
Windows XP #2: Firefox 3.5, Chrome, Internet Explorer 7, Opera 9, Maxthon 2
Windows XP #3: Firefox 3.5, Chrome, Internet Explorer 8, Opera 9, Maxthon
I'd donate an Ubuntu VM or two, but... they don't wanna start up at this point. shrug
This may not help, I dunno, but I'm certainly not using the computer. Have a blast, and good luck!
I think it is safe to conclude that browser-based crowdsourcing is not a compelling approach to numerical computation.
Contests are usually held to fire up peoples creativity and this idea to solve it via the browser as an ad-hoc cluster is really pretty creative.
Personally I think to try to solve this contest by brute forcing it is changing it in to a simple pissing contest between the various hardware / software combination, I'm sure some guy with an fpga kit will do a lot better than the CUDA competitors.
It would be nicer if someone discovered a previously undetected flaw and solved the contest through a backdoor. that would be hacker news :)
For comparison, this guy's distributed JS implementation just reached 1B a few hours ago: http://twitter.com/wondersquirrel/status/2750527789
If Engine Yard was trying to promote their cloud services with this contest it's rather ironic it appears it will probably be won be a few desktop computers with high end GPUs, which cloud hosts usually don't even have.
CUDA is pretty neat :)
Terrific idea and implementation. I have 10 tabs on Chrome. Good luck.
As far as I can tell, the browsers only contact him if they find a string with a shorter hamming distance, otherwise it's entirely offline, including picking random words.