Hash sort is surprisingly fast: for x in [0 ... VA.length] ind = VA.get(x)-1 VA.swap(x, ind + VA.length) for x in [0 ... VA.length] VA.swap(x, x + VA.length)
That's pretty cool. Is that related to this? http://arxiv.org/abs/cs/0408040
Show HN: Write a sort, watch it go
81–89 of 89 posts
Re: Show HN: Write a sort, watch it go
#82I love the stats on the side. Knowing how many comparisons and swaps occur really shows the complexity of the algorithms. And to segue into my own area of interest with sorting, it would be awesome to see cache and branch behaviour too (though of course this running in the browser, it's not exactly the real behaviour, but still).
How would you expect such things to be calculated? Not sure exactly what you're looking for.
Well, they would need to be simulated.
Re: Show HN: Write a sort, watch it go
#83Earlier quoted context omitted.
How would you expect such things to be calculated? Not sure exactly what you're looking for.
Well, they would need to be simulated.
Cache behavior simulation would be kind of a pain to implement, but I might give it a shot at some point. What is branch behavior? I'm not familiar with the term.
Re: Show HN: Write a sort, watch it go
#84Earlier quoted context omitted.
Well, they would need to be simulated.
Cache behavior simulation would be kind of a pain to implement, but I might give it a shot at some point. What is branch behavior? I'm not familiar with the term.
Yeah, I can see that. A big problem is that the set sizes where cache effects start to come into effect are much larger than the sizes you're modelling. A level 1 cache is going to have 4K, which is at least 5x the size you're modelling by default. But you can probably use play sizes, like a cache which only holds 16 or 32 ints.
By branch behaviour, I mean branch prediction. I did some research (http://paulbiggar.com/research/#sorting-tr) before that showed that branch prediction is really important for sorts. For example, insertion sort is way better than selection sort, and radix sort has really really good branch prediction properties, making it beat quicksort (well, this is LSB radixsort, and I think you implemented MSB radixsort, but no doubt it applies somewhat).
So for the branch simulation, implement a 2 bit dynamic saturating counter, and note the number of mispredictions. There are simpler and more complex predictors, but that's probably the simplest that's a reasonable approximation of real life.
Re: Show HN: Write a sort, watch it go
#85Hash sort is surprisingly fast: for x in [0 ... VA.length] ind = VA.get(x)-1 VA.swap(x, ind + VA.length) for x in [0 ... VA.length] VA.swap(x, x + VA.length)
That's cheating somehow...
Trading a tremendous amount of memory for speed. Try replacing a list of integers with a list of Images. You might lock up the browser.
Re: Show HN: Write a sort, watch it go
#86Earlier quoted context omitted.
Speaking of pain inducing, I found watching the bubble sort very pain inducing! I've always known it was slow compared to other options, but this make you never want to see the thing mentioned again!
I know Bubble sort is "bad", but there's no reason to make it worse than it needs to be. The current algorithm continues comparing the items that have already "bubbled" (or in this case, "sunk") by iterating the whole length on each pass, rather than shorting the loop to only consider the unsorted portion. A minor tweak is (changed lines marked with #): bubbleSort = -> VA.locals.swapped = true y = VA.length # grab in…
Neat. I came back 5 hours later, and the change was live. Thanks. (I was going to submit a change via Git when I got home, but you beat me to it!)
Re: Show HN: Write a sort, watch it go
#87Re: Show HN: Write a sort, watch it go
#88Implemented my own quicksort that seems to have better performance than the built-in one.
q = (lo, hi) =>
# highlight range
VA.persistHighlight([lo..hi])
p = VA.get(lo)
l = lo
r = hi
# test pivot position
t = false
while (l lo)
q(lo, l - 1)
if (hi > l + 1)
q(l + 1, hi)
q(0,VA.length - 1)Re: Show HN: Write a sort, watch it go
#89Earlier quoted context omitted.
Cache behavior simulation would be kind of a pain to implement, but I might give it a shot at some point. What is branch behavior? I'm not familiar with the term.
Yeah, I can see that. A big problem is that the set sizes where cache effects start to come into effect are much larger than the sizes you're modelling. A level 1 cache is going to have 4K, which is at least 5x the size you're modelling by default. But you can probably use play sizes, like a cache which only holds 16 or 32 ints. By branch behaviour, I mean branch prediction. I did some research ( http://paulbiggar.co…
I'll definitely implement a cache model to show cache behavior. I'm not sure branch prediction is realistic, though; I'm not actually parsing the code myself, so finding the branch points would be a lot of extra work. I'm considering a scheme where you have to call an extra function inside each branching statement to get useful branch prediction results. Something along the lines of:
for x in foreach([1...VA.length], "for1")
y = 0
while branch(VA.gt(x, y), "while1")
y++
if branch(y == x, "if1")
break
VA.insert(x, y)