Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Hashed sorting is typically faster than hash tables

reiner.org

Post reply on HN
Print view View original

61–67 of 67 posts

Re: Hashed sorting is typically faster than hash tables

#61

Post by gizmo686 »

tomp wrote: post #45

Very interesting and cool article, if you love low-level optimisation (like myself!) Interestingly, recently I've been thinking that basically the Big-O notation is essentially a scam, in particular the log(N) part. For small values of N , log(N) is essentially a constant, O(N) . For large values, even so-called linear algorithms (e.g. linear search) are actually O(N log(N)) , as the storage requirements for a single…

It is common to use Õ as a variant of O which ignores logorithmic factors.

Another reason to do this is that O(1) is typically a lie. Basic operations like addition are assumed to be constant time, but in practice, even writing down a number, n, is O(log(n)). More commonly thought of as O(b) where b is the bit-length of n.

Re: Hashed sorting is typically faster than hash tables

#62

Post by tialaramex »

randomNumber7 wrote: post #60
tialaramex wrote: post #29

Earlier quoted context omitted.

Do-What-I-Mean isn't possible. What Rust does give you is Do-What-I-Say which mostly leaves the problem of saying what you mean, a significant task but one that is hopefully what software engineering was training you to be most effective at. One important trick is ruling out cases where what you said is nonsense. That can't be what you meant so by ruling it out we're helping you fall into the pit of success and Rust…

All programming languages do what you say, the question is more about how easy it is to say something inappropriate. For me Rust rarely hits the sweet spot since there are easier languages for high level programs (python, C#, Swift...) and for low level programs you usually want to do unsafe stuff anyway. I can see usefull applications only where you cannot have a garbage collector AND need a safe high level language…

> All programming languages do what you say

By definition the Undefined Behaviour can't have been what you meant. So, all the languages where you can just inadvertently "say" Undefined Behaviour aren't meaningfully achieving this goal.

I must say I'm also extremely dubious about some defined cases. Java isn't UB when we try to call abs() on the most negative integer... but the answer is just the most negative integer again, and I wonder whether that's what anybody meant.

Re: Hashed sorting is typically faster than hash tables

#63

Post by tialaramex »

bluecalm wrote: post #36
tialaramex wrote: post #35

Earlier quoted context omitted.

> it would be pointless for me to try to code an optimized quick sort in it. Perhaps more so than you've realised. Hint: Rust's old unstable sort was its take on the pattern defeating quicksort. The article is talking about the new unstable sort which has better performance for most inputs. Rust uses monomorphization and its function types are unique, so the trick you're used to with a macro is just how everything wo…

The trick is not about macros but about removing function calls altogether. Macros are there only to generate functions for specific types. The way the trick works is to implement the stack manually and put indexes there instead of passing them as function arguments. This removes a lot of overhead and makes the implementation I linked to significantly faster than C's and C++'s standard library implementation.

Because this function is internal Rust doesn't need to give it the Itanium ABI so the recursion won't incur the overhead you're imagining.

Re: Hashed sorting is typically faster than hash tables

#64

Post by alain94040 »

shoo wrote: post #10
aDyslecticCrow wrote: post #9

Earlier quoted context omitted.

That is what baffles me. The difference in big O complexity should be more visible with size, but thats where it looses to the "worse" algorithm. I could imagine the hash table wins again beyond a even greater threshold. Like what about 120GB and beyond?

The analysis in the "Why does sorting win?" section of this article gave us a way to estimate that threshold. Here's my attempt at it, based on that analysis: Suppose each item key requires s bytes For the hash table, assuming s The bandwidth to sort one key is p(N) * 2 * s where p(N) is the number of passes of 1024-bucket radix sort required to sort N elements, and 2 comes from 1 read + 1 write per 1024-bucket radix…

>This analysis would suggests a 2.7× speedup vs. hash tables: 128 bytes vs. 48 bytes of memory traffic per uint64

It's ok to waste bandwidth, it doesn't directly impact performance. However, the limitation you are hitting (which directly impacts performance) is the number of memory accesses you can do (per cycle for instance) and the latency of each memory access. With linear access, after some initial read, data is ready instantly for the CPU to consume. For scattered data (hash tables), you have to pay a penalty on every read.

So the bandwidth ratio is not the right factor to look at to estimate performance.

Re: Hashed sorting is typically faster than hash tables

#65

Post by randomNumber7 »

tialaramex wrote: post #62
randomNumber7 wrote: post #60

Earlier quoted context omitted.

All programming languages do what you say, the question is more about how easy it is to say something inappropriate. For me Rust rarely hits the sweet spot since there are easier languages for high level programs (python, C#, Swift...) and for low level programs you usually want to do unsafe stuff anyway. I can see usefull applications only where you cannot have a garbage collector AND need a safe high level language…

> All programming languages do what you say By definition the Undefined Behaviour can't have been what you meant. So, all the languages where you can just inadvertently "say" Undefined Behaviour aren't meaningfully achieving this goal. I must say I'm also extremely dubious about some defined cases. Java isn't UB when we try to call abs() on the most negative integer... but the answer is just the most negative integer…

I think you have a misunderstanding of undefined behavior.

> So, all the languages where you can just inadvertently "say" Undefined Behaviour aren't meaningfully achieving this goal.

This is absolute nonsense.

You should generally avoid writing programs with undefined behavior.

C and Java can be used to write programs with defined behavior (even if you can't) that are used by billions of users every day.

Re: Hashed sorting is typically faster than hash tables

#66

Post by bluecalm »

tialaramex wrote: post #63
bluecalm wrote: post #36

Earlier quoted context omitted.

The trick is not about macros but about removing function calls altogether. Macros are there only to generate functions for specific types. The way the trick works is to implement the stack manually and put indexes there instead of passing them as function arguments. This removes a lot of overhead and makes the implementation I linked to significantly faster than C's and C++'s standard library implementation.

Because this function is internal Rust doesn't need to give it the Itanium ABI so the recursion won't incur the overhead you're imagining.

It's not my imagination. It's my experience with benchmarking it. The implementation I linked to is 2x (or even more on relatively short arrays) faster than standard library C++ sort. Is Rust sort as fast?

Re: Hashed sorting is typically faster than hash tables

#67

Post by tialaramex »

randomNumber7 wrote: post #65
tialaramex wrote: post #62

Earlier quoted context omitted.

> All programming languages do what you say By definition the Undefined Behaviour can't have been what you meant. So, all the languages where you can just inadvertently "say" Undefined Behaviour aren't meaningfully achieving this goal. I must say I'm also extremely dubious about some defined cases. Java isn't UB when we try to call abs() on the most negative integer... but the answer is just the most negative integer…

I think you have a misunderstanding of undefined behavior. > So, all the languages where you can just inadvertently "say" Undefined Behaviour aren't meaningfully achieving this goal. This is absolute nonsense. You should generally avoid writing programs with undefined behavior. C and Java can be used to write programs with defined behavior (even if you can't) that are used by billions of users every day.

No, I'm pretty sure I understand the nature of Undefined Behaviour well.

It's not nonsense, since writing this I have watched several videos in which people playing with newer languages say [of Rust] "Oh, I guess I got that wrong, I'll fix it" when Rust's compiler tells them what they wrote is nonsense, but they do not make similar corrections in the languages where what they wrote is UB because it's never brought to their attention.

It's human nature, I assume what I wrote is correct, the machine accepts it, I guess it was correct. Right? Nope, for several of these languages - including C and the various "C successor" languages like Zig or Odin - the compiler blithely accepts nonsense and it has UB - that's my point here.

You lump together Java and C at the end which is silly. Java doesn't have UB except narrowly via clearly labelled "it's unsafe to use this" features. On the other hand in C even adding 200 and 300 together may be Undefined Behaviour in some contexts and you need a compiler vendor chosen flag if you even want to be alerted to the most obvious examples of this because the language doesn't care that you're about to shoot yourself in the foot.

Post reply on HN