61–70 of 84 posts
Earlier quoted context omitted.
I've been interested in this since your presentation in May; any plans to release the source any time soon? (Here's where I hope I'm asking a dumb question and you already have, but I haven't been able to find it.)
Hey, the open source release will coincide with the FOSDEM presentation, so in a little under three weeks it will be under my Github account github.com/orlp.
Earlier quoted context omitted.
Because without the insertion cost of fixed locations, insertion sort is also NlogN: just a binary search per element.
Hey wait, good point, what the heck kind of data structure even is a stack of papers? You can insert like a linked list but hop around like an array.
Earlier quoted context omitted.
Hey wait, good point, what the heck kind of data structure even is a stack of papers? You can insert like a linked list but hop around like an array.
Only for reasonably small stacks. Insertions at random indices won't stay O(1) when you're dealing with 100k pages and more – i.e., when you can't pick them up in one movement.
At FOSDEM 2023 I will be presenting glidesort in the Rust room. It is a new stable sorting algorithm that is a hybrid of quicksort and mergesort which is much faster for random data, while still taking full advantage of pre-existing order or inputs with many duplicates. On an Apple M1 in Rust the latest version is ~4.5x faster than the stdlib slice::sort for sorting 2^25 random integers while using 4 times less extra…
Earlier quoted context omitted.
That's probably on me... If I had to do it again, I would make it stable now.
Luckily this is a backwards-compatible change so sorokod should lobby the Dart team.
https://github.com/dart-lang/sdk/issues/433#issuecomment-108...
At FOSDEM 2023 I will be presenting glidesort in the Rust room. It is a new stable sorting algorithm that is a hybrid of quicksort and mergesort which is much faster for random data, while still taking full advantage of pre-existing order or inputs with many duplicates. On an Apple M1 in Rust the latest version is ~4.5x faster than the stdlib slice::sort for sorting 2^25 random integers while using 4 times less extra…
How does the speed compare to a well optimized radix sort?
I would assume that they're faster, especially if using SIMD.
Earlier quoted context omitted.
Luckily this is a backwards-compatible change so sorokod should lobby the Dart team.
Is it though? Or is Dart-Js not a thing any more? https://github.com/dart-lang/sdk/issues/433#issuecomment-108...
Earlier quoted context omitted.
What are you talking about? This is in a JS engine, where by design all code is untrusted. If you are a JS engine, then arbitrary code execution, failure to terminate, or crashing is never an acceptable outcome, regardless of how bad the code is, because again, you're dealing with untrusted input. The assumption for a JS engine is necessarily that all code is malicious.
Obviously it may never crash, and it never did, even with a bad comparison function. But the JS engine does not protect against the page containing JS code that loops forever. How would it even do that? Edit: Perhaps some misunderstanding: V8 "just used Quicksort", but it never used the qsort function from the C library. That would not have worked with garbage collection, since you can have a garbage collection in th…
But the point is that the general quicksort algorithm does a bunch of unsafe memory accesses if the comparator is unstable (either directly or by modification of the sorted data). As demonstrated by every qsort implementation going wrong in unsafe ways in such a scenario.
Now maybe you used a version of qsort that actually made sure it wasn’t going out of bounds and what not and did … something? When that occurred, and saying what that something was would be a reasonable answer.
As for qsort() not being an option due to gc, that’s only a problem due to v8’s gc - JSC for instance could just use qsort or what not if it was sure the sort was consistent.
Earlier quoted context omitted.
How does the speed compare to a well optimized radix sort?
I haven't compared because they're apples and oranges. The radix sorts do not allow a custom comparison function. I would assume that they're faster, especially if using SIMD.