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

Speed of Rust vs. C

kornel.ski

Post reply on HN
Print view View original

531–540 of 546 posts

Re: Speed of Rust vs. C

#531

Post by roca »

snovv_crash wrote: post #498
roca wrote: post #401

Earlier quoted context omitted.

When your loop body uses complex library APIs over complex data it's still hard to be confident in C++ that everything's threadsafe and you're avoiding data races. Maybe it's not so hard if you're in a domain like HPC where the libraries you use are designed specifically to be used with data parallelism. But when you're pulling together code from different sources that may or may not have been used in an aggressively…

If the APIs that you're interacting with are side-effect free then it's easy. If they are full of side effects, then they aren't written with multithreading in mind and you wouldn't be able to even compile it in Rust. C++ just takes off the training wheels.

It's a bit more complicated than that, because code can be thread-safe but not side-effect-free, but basically you're just restating what I said. C++ makes it hard to be sure code is really safe to use across threads, which means in practice developers should be more reluctant to do so.

Re: Speed of Rust vs. C

#532

Post by mlindner »

nyc_pizzadev wrote: post #219

Shouldn’t this be Rust vs C++? C++ has a lot more parallels to Rust. Both are big, complex, and safe languages that can tuned for high performance. Infact, I would like to see more comparisons of Rust and C++ in the future.

Rust replaces uses of C in many ways that C++ never could so I think the comparison is apt. There isn't extensive use of C++ in the embedded world nor is it used much for writing kernel drivers, but Rust is making big inroads into both of those arenas.

Re: Speed of Rust vs. C

#533

Post by eru »

burntsushi wrote: post #521
eru wrote: post #493

Earlier quoted context omitted.

I suspect Don Stewart might be able to do it in Haskell. That's basically by knowing enough about GHC to carefully trigger all the relevant optimizations.

Hah. I'm highly skeptical. But I suppose if anyone could do it, it'd be him. I would certainly learn something. :-) I've tried optimizing Haskell code myself before. It did not go well. It was an implementation of the Viterbi algorithm actually. We ported it to Standard ML and C and measured performance. mlton did quite well at least. We published a paper about the process of writing Viterbi in Haskell in ICFP a few…

Very interesting!

I suspect you could make a very Haskell-like language that's also really fast, but you'd have to base it on linear types from the ground up, and make everything total by default. (Hide non-total parts behind some type 'tag' like we do with IO in current Haskell (and have something like unsafePerformPartial when you know your code is total, but can't convince the compiler).)

That way the compiler can be much more aggressive about making things strict.

Re: Speed of Rust vs. C

#534

Post by eru »

burntsushi wrote: post #518
eru wrote: post #491

Earlier quoted context omitted.

> No, it doesn't. It's only theoretically easy to implement. Oh, I didn't say anything about easy! I am on and off working on a Haskell re-implementation (but with GADTs and in Oleg's tagless final interpreter style etc, so it's more about exploring the type system). > In practice, they explode the size of the underlying FSM. You may be right, but that's still better than the gymnastics you'd have to do by hand to ge…

Yeah sorry, I've gotten asked this question a lot. The issue is that building a production grade regex engine---even when it's restricted to regular languages---requires a lot more engineering than theory. And these particular features just don't really pull their weight IMO. They are performance footguns, and IMO, are also tricky to reason about inside of regex syntax. If you get something working, I'd love to look…

For my current attempts, I bit off more than I could chew:

I tried to build a system that not only recognizes regular languages, but also serves as a parser for them (a la Parsec).

The latter approach pushes you to support something like fmap, but the whole derivatives-based approach needs more 'introspection' so support general mapping via fmap (ie a->b) is out, and you can only support things that you have more control over than functions.

(And in general, I am doing bifunctors, because I want the complement of the complement be the original thing.)

Sorry, if that's a bit confused.. If I was a better theoretician, I could probably work it out.

I haven't touched the code in a while. But recently I have thought about the theory some more. The Brzozowski derivative introduced the concept of multiplicative inverse of a string. I am working out the ramifications of extending that to the multiplicative inverse of arbitrary regular expressions. (The results might already be in the literature. I haven't looked much.)

I don't expect anything groundbreaking to come out of that, but I hope my understanding will improve.

> And these particular features just don't really pull their weight IMO. They are performance footguns, and IMO, are also tricky to reason about inside of regex syntax.

Well, in theory I could 'just' write a preprocessor that takes my regex with intersection and complement and translates it to a more traditional one. I wouldn't care too much if that's not very efficient.

I'm interested in those features because of the beauty of the theory, but it would also help make production regular expressions more modular.

Eg if you have a regular expression to decide on what's a valid username for someone to sign up to your system. You decide to use email addresses as your usernames, so the main qualification is that users can receive an email on it. But because they will be visible to other users, you have some additional requirements:

'.{0,100} & [^@]@[^@] & not (.(root|admin|).@.) & not (..*)'

That's a silly example. I think in production, I would be more likely to see something as complicated as this in eg some ad-hoc log parsing.

> The issue is that building a production grade regex engine---even when it's restricted to regular languages---requires a lot more engineering than theory.

Amen to that!

Re: Speed of Rust vs. C

#535

Post by eru »

burntsushi wrote: post #520
eru wrote: post #492

Earlier quoted context omitted.

I've made some attempts, but nothing production grade. About large character classes: how are those harder than in approaches? If you build any FSM you have to deal with those, don't you? One way to handle them that works well when the characters in your classes are mostly next to each other unicode, is to express your state transition function as an 'interval map' What I mean is that eg a hash table or an array lets…

> About large character classes: how are those harder than in approaches? If you build any FSM you have to deal with those, don't you? I mean specifically in the context of derivatives. IIRC, the formulation used in Turon's paper wasn't amenable to large classes. Yes, interval sets work great: https://github.com/rust-lang/regex/blob/master/regex-syntax/... This is why I asked if a production grade regex engine based…

> If I'm remembering correctly, I think the problem with derivatives is that they jump straight to a DFA. You can't do that in a production regex engine because a DFA's worst case size is exponential in the size of the regex.

Oh, that's interesting! Because I actually worked on some approaches that don't jump directly to the DFA.

The problem is the notion of (extended) NFA you need is quite a bit more complicated when you support intersection and complement.

Re: Speed of Rust vs. C

#536

Post by igouy »

pornel wrote: post #285
ReactiveJelly wrote: post #225

I'm a Rust evangelist, but the article is titled "Speed of Rust vs. C" and doesn't seem to contain even one benchmark. For fuck's sake.

There's already The Benchmarks Game and ixy-languages if you want hard numbers. Maximum speeds are already explored. I wanted to discuss an aspect that's not typically covered by pure benchmarks: what can you expect from normal day-to-day use of these languages. Not fine-tuned hot loops, but a "median" you can expect when you just need to get shit done. If I tried to write a benchmark code to represent average, pract…

Or start at the bottom of the measurements and work up from the 28.55s g++ program to the 0.84s g++ program :-)

https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

Re: Speed of Rust vs. C

#537

Post by malkia »

johncolanduoni wrote: post #84
malkia wrote: post #47

Earlier quoted context omitted.

The bigger issue is coordinating these threads ("workers") with threads from other processes, there is nothing on Windows and Linux to do so, then again I haven't had much experience with Grand Dispatch (OSX) to know if it's worth. Windows has new thread pool API, but even TBB or ConCRT do not use it. (though the new par-support in STL (msvc) does).

Windows, Linux and macOS all have inter-process mutexes and condition-variable-ish constructions. Windows has named mutex, semaphores, and events that can be opened by multiple processes, and the pthread API supports mutex and condition variables in shared memory. Linux additionally supports its futex primitive in shared memory regions (which is how the pthread API is implemented on that OS).

Thanks! Wasn't aware of this possible use, and havent' used much explicitly named pipes/mailslot except for direct communication. Wondering how would still work - I mean something ought to be the "task manager" in all that, coordinating.

Why else come up with this - https://docs.microsoft.com/en-us/windows/win32/procthread/th...?

Re: Speed of Rust vs. C

#538

Post by randomswede »

TazeTSchnitzel wrote: post #195
scorpion95 wrote: post #90

Earlier quoted context omitted.

Which form of Rust parallelism did you choose? I’ve read that the old one sucks. Certainly Rust is different beast than C. Code converted from C to Rust seems much more voluminous. Perhaps it’s easier to maintain if you know Rust well? I cannot believe at first that Rust is ever more performant than C, as C could be made parallel and seems more barebones. One of the languages that CUDA can be used with is C, so I sus…

C being barebones does not mean it is faster. Because it has such weak typing and gives a huge amount of programmer freedom, compilers have to do a lot of work to be able to understand a C program well enough to optimise it. Rust, on the other hand, requires the programmer to give the compiler more information about what they're doing. A very simple example: void foobar(struct foo *f) { f->a += 2; foo(); f->a += 2; b…

If you can have "one mutable" and "more than one non-mutable" reference (not sure if this is the case), you still cannot safely do that optimization, as foo() and bar() could in principle be reading f.a and the optimized version would then not have the correct values of f.a when foo() and bar() are called.

Note, I genuinely don't know if this caveat applies to Rust. But, m general, not only mutable references need to be considered.

Re: Speed of Rust vs. C

#539

Post by petdance »

cb321 wrote: post #403
burntsushi wrote: post #369

Earlier quoted context omitted.

You're missing the context I think. Look at what I was responding to in my initial message in this thread: > If you have an architecture where you can afford real parallelism you can afford higher level languages anyway. My response is, "no you can't, and here's an example." > but any language mature enough to have an impl/way to not have arbitrary performance ceilings needs access to inline assembly/SIMD If you port…

Ok. "Afford parallelism => afford high level" with the implication of HL=slow does sound pretty off base. So, fair enough. FWIW, as per your subtle claim, it all seems pretty hot spot optimizable to me, at least if you include the memchr/utf8-regex engine in "hot spot". I do think the entire framing has much measurement vagueness ("hot", "vast majority", "levelness", and others) & is unlikely to be helpful, as explai…

> I do not know of a competitor who has put the care into such a tool to even try to measure, though.

As an aside, I'm the author of ack, and I would ask that folks not use the word "competitor" to describe different projects in the same space. Speaking for me/ack and burntsushi/ripgrep, there is absolutely no competition between us. We have different projects that do similar things, and neither of us is trying to best the other. We are each trying to make the best project we can for the needs we are looking to fill. ripgrep won't replace ack, ack won't replace ripgrep, and neither one will replace plain ol' grep. Each has its place.

I believe this so strongly that I created a [feature comparison chart](https://beyondgrep.com/feature-comparison/) comparing various greplike tools, and a related blog post I wrote on this: [The best open source project for someone might not be yours, and that's OK](https://blog.petdance.com/2018/01/02/the-best-open-source-pr...)

Re: Speed of Rust vs. C

#540

Post by supergarfield »

loeg wrote: post #349
supergarfield wrote: post #326

Earlier quoted context omitted.

> and Python still does AFAIK Don't you sort of have to do that if you're writing your own garbage collector, though? I guess for a simple collector you could maintain lists of allocated objects separately, but precisely controlling where the memory is allocated is important for any kind of performant implementation.

Python does refcount-based memory management. It's not a GC design. You don't have to retain objects in an internal linked list when the refcount drops to zero, but CPython does, purely as a performance optimization. Type-specific free lists (just a few examples; there are more): * https://github.com/python/cpython/blob/master/Objects/floato... * https://github.com/python/cpython/blob/master/Objects/tupleo... And als…

Thanks for the links! I wasn't aware of the PyMem_ layer above, the justification for that does sound bad.

But Python runs a generational GC in addition to refcounting to catch cycles (https://docs.python.org/3/library/gc.html): isn't fine control over allocation necessary for that? E.g. to efficiently clear the nursery?

Post reply on HN