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

Rust is now overall faster than C in benchmarks

benchmarksgame-team.pages.debian.net

Post reply on HN
Print view View original

411–420 of 445 posts

Re: Rust is now overall faster than C in benchmarks

#411

Post by jstimpfle »

littlestymaar wrote: post #204
dan-robertson wrote: post #197

Earlier quoted context omitted.

The reason that C programs often perform well is that it’s so incredibly hard to do anything at all in C (especially something reliable) that one can usually only do the simplest thing possible and this typically means simple data structures, simple algorithms and arrays. In many ways, modern CPUs are particularly designed to run the machine code generated by C compilers on typical C code like this. Pointers and memo…

> The reason that C programs often don’t perform as well as an equivalent rust program[1] is that it’s so incredibly hard to do anything at all in C (especially something reliable) that one can usually only do the simplest thing possible and this typically means simple data structures, simple algorithms and arrays Brian Cantrill talks[1] about exactly this: in his C version he was using AVL trees because they are eas…

So he's comparing the AVL tree he wrote himself to a B-tree optimized to death by someone else?

Out of interest though, does he mention somewhere which actual implementation he used?

Re: Rust is now overall faster than C in benchmarks

#412

Post by jstimpfle »

Matthias247 wrote: post #93

Apart from those benchmark games a lot of real world C is a lot less performant than people think it might be. I spent a fair amount of time reviewing C code in the last 5 years - and things that pop up in nearly every review are costly string operations. Linear counts due to the use of null terminated strings and extra allocations for substrings to attach null terminators, or just deep copies because ownership can’t…

Slow code bottlenecked by string operations is probably just bad, though - no matter which way you code your strings. Strings are not what computers like to do. Computers like integers and subscripting operations. Strings can make sense for inter-process scenarios (for example, file paths are usually the right thing and you don't want to reference files with inodes).

There is a culture of bad C code from the 90s - especially C code written in OOP-y ways where that was never necessary. Like, calling malloc() + free() for every little thing instead of more structured memory management. A lot of that code is written in C not with a efficiency or elegance mindset but simply because C was the language that you wrote programs in.

Re: Rust is now overall faster than C in benchmarks

#413

Post by igouy »

burntsushi wrote: post #409
igouy wrote: post #404

Earlier quoted context omitted.

> It is indeed a problem. There are ways to address it. Please make a specific suggestion.

I did. You just didn't like their costs. Which is reasonable. They do have costs. I just happen to think they are worth it. For analysis, it increases review time and increases the burden on contributors. The extent to which any one person can review all analyses isn't clear to me, and they would likely need to rely on contributors to self regulate them. But I would expect the maintainers to review them for some mini…

> I did. … As for the disclaimer, I don't really see the point of being more specific.

I really was asking for a specific suggestion for "disclaimers on the web site more discoverable".

> A simple suggestion might be to put it at the top of each page or even in the description of each benchmark. I don't know how much this would help things. Maybe people would still just ignore it.

https://www.reddit.com/r/rust/comments/kpqmrh/rust_is_now_ov...

People see what they are looking for.

Re: Rust is now overall faster than C in benchmarks

#414

Post by jstimpfle »

leetcrew wrote: post #292
loup-vaillant wrote: post #255

Earlier quoted context omitted.

> In my opinion, hash tables, btrees and the like in the standard library should probably swap to flat lists internally when the number of items in the collection is small. I'm surprised more libraries don't do that. If I recall correctly, the STL provides guarantees that prevents it from taking advantage of flat lists. I think some containers (not arrays) guarantee that they don't move the address of whatever they'r…

> Likewise, I believe I have heard of small string optimisation being impossible with std::string for similar reasons. not impossible, SSO is implemented to some extent in most mainstream c++ compilers.

I thought that was impossible because it breaks references when moving strings.

Re: Rust is now overall faster than C in benchmarks

#415

Post by WalterBright »

BruceEel wrote: post #373
WalterBright wrote: post #261

Earlier quoted context omitted.

D uses slices for strings, which also gives D a big performance boost over C whenever strings are in play.

Walter, can you elaborate on this, are D's slices functionally equivalent to C++'s string_view? I.e. no copying as long no 'ASCIIZ-dependent' code is involved?

D strings are a simply a pointer/length pair. Substrings can be extracted with no alloc/copying necessary. The length can be determined without loading the string into the cache and scanning it.

Those two features make for big speed improvements.

Re: Rust is now overall faster than C in benchmarks

#416

Post by jstimpfle »

josephg wrote: post #206
vbezhenar wrote: post #153

Earlier quoted context omitted.

It might be fast, but it'll load CPU caches with that data and it'll evict another useful data. Which means that while this particular code will be fast or at least not very slow, some other code will be slow because its data have to be fetched again. I have no idea whether that matters or even easy to measure...

> I have no idea whether that matters or even easy to measure... It is reasonably easy to measure, and the GP is about right. I've measured a crossover point of around a few hundred items too. (Though I'm sure it'll vary depending on use case and whatnot.) I made a rope data structure a few years ago in C. Its a fancy string data structure which supports inserts and deletes of characters at arbitrary offsets. (Design…

Thank you, I tried the rope, and I ran a benchmark that creates a rope of length 1G by repeatedly inserting 1023 bytes at random positions. Some notes:

When I changed the hardcoded node size from 136 to 1024 bytes, time went down from 3.6 secs to 2.6 secs on my laptop. It kind of plateaued at 1024 bytes. I didn't do more extensive testing.

What's the rationale for the choice of 136? A cache line is usually 64, so the CPU will always end up loading a multiple of that in any case.

When I did a rope implementation myself (I don't know how it compares in terms of performance) I think I ended up with nodes of 4096 or 8192 bytes size. That was based on a Red-black tree. When I load ~1Gig of data, even with a node size of 4096, there will still be 2^18 nodes, meaning each access requires sth. like 17 child traversals, which seems a lot to me. So I can't see myself going down to 200 bytes or less.

Re: Rust is now overall faster than C in benchmarks

#417

Post by jstimpfle »

snicker7 wrote: post #297
vbezhenar wrote: post #153

Earlier quoted context omitted.

It might be fast, but it'll load CPU caches with that data and it'll evict another useful data. Which means that while this particular code will be fast or at least not very slow, some other code will be slow because its data have to be fetched again. I have no idea whether that matters or even easy to measure...

The CPU will load less cache data with linear searches. This is because you will have less cache misses. Less cache misses == less loading from memory. With pointer-heavy data structures, you load more from memory, and most of the stuff you do load is useless.

A binary tree might require you to visit only O(log2(N)) of your data, while a linear array on average requires you to visit one half. How does that correspond to less loading from memory?

Linear arrays are often faster, not because they require fewer memory loads, but because the cache has intelligence built in (the prefetcher) that loads some memory in advance even before the code requests it. That intelligence works way better with linear array scans than with pointer chasing. (I'm not sure if these loads will count as cache misses or not).

Re: Rust is now overall faster than C in benchmarks

#418

Post by igouy »

burntsushi wrote: post #409
igouy wrote: post #404

Earlier quoted context omitted.

> It is indeed a problem. There are ways to address it. Please make a specific suggestion.

I did. You just didn't like their costs. Which is reasonable. They do have costs. I just happen to think they are worth it. For analysis, it increases review time and increases the burden on contributors. The extent to which any one person can review all analyses isn't clear to me, and they would likely need to rely on contributors to self regulate them. But I would expect the maintainers to review them for some mini…

> I think a lot of people would benefit from an explanation of the performance characteristics of the program.

For sure!

And that's way beyond the modest aims of the benchmarks game.

> People regularly misinterpret benchmarks … From what I can tell, you as the maintainer have done very little to address that.

Seems to me that misinterpretation is not something that is effectively addressed by website content; it's something that is effectively addressed by responding to what people say when they discuss benchmarks in forums like HN and proggit and … one person at a time.

> … you can just respond and tell me to go do it. I think that's a cheap response…

It isn't intended as a brush-off.

otoh as you show on proggit, it's when you "Just sit down and actually try to plan out what you would do." that you start to understand what is involved.

otoh I'd like to see others do all that stuff the benchmarks game does not do, in whatever way they choose https://pybenchmarks.org/

Re: Rust is now overall faster than C in benchmarks

#419

Post by jstimpfle »

martincmartin wrote: post #96
Matthias247 wrote: post #93

Apart from those benchmark games a lot of real world C is a lot less performant than people think it might be. I spent a fair amount of time reviewing C code in the last 5 years - and things that pop up in nearly every review are costly string operations. Linear counts due to the use of null terminated strings and extra allocations for substrings to attach null terminators, or just deep copies because ownership can’t…

Also lack of generics can make it slow, e.g. qsort() requires a function call for each comparison. So C++'s std::sort() can be significantly faster on an array of integers.

I love qsort! It's easy to use.

When I once tested std::sort against qsort (sorting 4-byte integer) I measure a 2x difference. So yes, definitely non-trivial, but it won't get much worse than that.

Have you ever seen a program that was slow because of a slow sorting routine?

If you ever need a fast sort (~ never) then the last thing you should do is use std::sort anyway. You should figure out what your data looks like and hand roll an implementation. For example, a radix sort is often possible to use, easy to implement, and much faster than std::sort.

Re: Rust is now overall faster than C in benchmarks

#420

Post by musicale »

unethical_ban wrote: post #370
musicale wrote: post #264

Earlier quoted context omitted.

> real world C is a lot less performant than people think it might be What is meant here? Fast? Reliable? Secure? Memory efficient? Power efficient? Easy to write? Easy to maintain? Quick to compile? Easy to debug? I have no illusions about the reliability/security/correctness of real-world C code, especially since it's usually not compiled with a memory-safe compiler or run with memory-safe libraries and runtime env…

I assume, since the submissions says is talking about something "faster in benchmarks", that he means "fast".

Yeah, I think you're right.

"Less performant" seems like a less clear (so to speak) way of saying "slower" (or maybe "less efficient" or simply "worse" in some instances.)

Post reply on HN