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

491–500 of 546 posts

Re: Speed of Rust vs. C

#491

Post by eru »

burntsushi wrote: post #473
eru wrote: post #464

Earlier quoted context omitted.

It couldn't figure it out from looking through ripgrep's website: does ripgrep support intersection and complement of expressions? Like eg https://github.com/google/redgrep does. Regular languages are closed under those operations after all.

No, it doesn't. It's only theoretically easy to implement. In practice, they explode the size of the underlying FSM. Moreover, in a command line tool, it's somewhat easy to work around that through the `-v` switch and shell pipelining. Paul's talk introduced redgrep is amazing by the way. Give it a watch if you haven't yet: https://www.youtube.com/watch?v=Ukqb6nMjFyk ripgrep's regex syntax is the same as Rust's regex…

> 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 get the same features out of a 'normal' regex.

> Moreover, in a command line tool, it's somewhat easy to work around that through the `-v` switch and shell pipelining.

Alas, that only works, if your intersection or complement happen at the top level. You can't do something like

(A & not B) followed by (C & D)

that way.

> Paul's talk introduced redgrep is amazing by the way. Give it a watch if you haven't yet: https://www.youtube.com/watch?v=Ukqb6nMjFyk

I have, and I agree!

Perhaps I'll try and implement a basic version of redgrep in Rust as an exercise. (I just want something that supports basically all the operations regular languages are closed, but don't care too much about speed, as long as the runtime complexity is linear.)

Re: Speed of Rust vs. C

#492

Post by eru »

burntsushi wrote: post #474
eru wrote: post #465

Earlier quoted context omitted.

> I played with making a regex library in rust. Which, as per RE2 design involves constructing graphs and glueing them together as the regex is traversed You could instead go with a derivatives approach. https://en.wikipedia.org/wiki/Brzozowski_derivative

Has anyone built a production grade regex engine using derivatives? I don't think I've seen one. I personally always get stuck at how to handle things like captures or the very large Unicode character classes. Or hacking in look-around. (It's been a while since I've given this thought though, so I'm not sure I'll be able to elaborate much.)

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 you build representations of mathematical functions that map points to values.

You want something that can model a step function.

You can either roll your own, or write something around a sorted-map data structure.

Eg in C++ you'd base the whole thing around https://en.cppreference.com/w/cpp/container/map/upper_bound (or https://hackage.haskell.org/package/containers-0.4.0.0/docs/... in Haskell.)

The keys in your sorted map are the 'edges' of your characters classes (eg where they start and end).

Does that make sense? Or am I misunderstanding the problem?

> I personally always get stuck at how to handle things like captures [...]

Let me think about that one for a while. Some Googling suggests https://github.com/elfsternberg/barre but they don't seem to support intersection, complement or stripping prefixes.

What do you want your capture groups to do? Do you eg just want to return pointers to where you captured them (if any)?

I have an inkling that something inspired by https://en.wikipedia.org/wiki/Viterbi_algorithm might work.

https://github.com/google/redgrep/blob/main/parser.yy mentions something about capture, but not sure if that has anything to do with capture groups.

Re: Speed of Rust vs. C

#493

Post by eru »

burntsushi wrote: post #351
pjmlp wrote: post #332

Earlier quoted context omitted.

Python isn't really something I would even think as possible example, Common Lisp, D, Nim, Swift, most likely.

So? I said, "higher level language." I didn't say, "Python specifically." I would guess D could do it. I don't know enough about Nim or Swift. I would learn something if Common Lisp did it. I'd also learn something if Haskell or Go did it.

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.

Re: Speed of Rust vs. C

#494

Post by electricshampo1 »

anonymousDan wrote: post #75
jandrewrogers wrote: post #17

Earlier quoted context omitted.

Data locality is everything for computational throughput. Having all data private to a single core is extraordinarily efficient compared to sharing data, and particularly mutable data, across cores. This creates a new problem: how do you balance load across cores? What if the workload is not evenly distributed across the data held by each core? Real workloads are like this! Fortunately, over the last decade, architec…

Can you point to any references/resources summarizing the latest cross-core dynamic load shedding techniques? Are they old techniques just now being applied in practice, or has something new been proposed?

I don't know about latest; but try look at

Scheduling Parallel Programs by Work Stealing with Private Deques https://hal.inria.fr/file/index/docid/863028/filename/full.p...

Re: Speed of Rust vs. C

#495

Post by lfairy »

jblow wrote: post #453
Rusky wrote: post #443

Earlier quoted context omitted.

> Okay, but if I do this everywhere, then I de facto don't have memory safety. No, that's not how this works. You write the unsafe code in one place and make sure it's correct (just like you'd do in C or Jai), and then you wrap it in a function signature that lets the compiler apply its memory safety checks to all the places that call it (this is what Rust gives you over C). This is still a meaningful improvement to…

> that lets the compiler apply its memory safety checks to all the places that call it My point is that those memory safety checks are now meaningless. > This is still a meaningful improvement to memory safety over C. No, it really isn't. What you are describing is almost exactly what you get in C.

So you're saying that Haskell's memory safety is meaningless too, because parts of its stdlib and runtime are written in C?

Re: Speed of Rust vs. C

#496

Post by pjmlp »

eru wrote: post #489
pjmlp wrote: post #329

Earlier quoted context omitted.

Python 3 has shown the world what happens when that is done without bringing the ecosystem along.

Haskell has also removed some features over time.

Haskell or GHC?

If you mean GHC, the language version is whatever the pile of configuration flags at each source file ends up meaning, some of them even contradict themselves.

Great for language research, which is Haskell main purpose in life, hardly a good idea for getting industry love.

Re: Speed of Rust vs. C

#497

Post by _vvhw »

_ph_ wrote: post #189
_vvhw wrote: post #181

Earlier quoted context omitted.

You are not factoring in the cost of context switches, and that many user applications today are memory-bound and not CPU-bound. It's one of the secrets exploited by the M1 chip, seen in how many more cache lines the CPU's LFB can fill concurrently compared to Intel chips and that these are now 128 byte cache lines instead of 64 byte cache lines.

Which context switches? With the Go model, I have exactly one thread per CPU, no context switches. And if you are memory-bound, why have more CPUs? But sure, there is a reason why the M1 has so stellar performance, it has one of the fastest single-thread performances and many applications do not manage to load more than 4 cores for common tasks - which partially is also a consequence of doing that is difficult in man…

> Which context switches? With the Go model, I have exactly one thread per CPU, no context switches.

Not in the user application model you were describing. Those threads would need to coordinate and communicate (for example, back to the user interface), and that implies context switches.

Unless you're thinking of a strictly isolated thread-per-core design (https://mechanical-sympathy.blogspot.com/2011/09/single-writ...), which means we are then in agreement.

> And if you are memory-bound, why have more CPUs?

Yes, exactly, and that's why parallelism can often make things worse: https://brooker.co.za/blog/2014/12/06/random.html

However, for independent processes, each additional CPU adds memory bandwidth (according to the NUMA model) because there's a concurrency limit to each CPU's LFB that puts an upper bound of 6 GB/s on filling cache lines for cache misses (even if the bandwidth of your memory system is actually much higher): https://www.eidos.ic.i.u-tokyo.ac.jp/~tau/lecture/parallel_d...

Re: Speed of Rust vs. C

#498

Post by snovv_crash »

roca wrote: post #401
snovv_crash wrote: post #397

Earlier quoted context omitted.

I've used them extensively in C++. Doing it manually by managing your own threads is a pain, but simple OpenMP based parallel loops work really well, and also supports tasks like building vectors and simple reductions.

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.

Re: Speed of Rust vs. C

#499

Post by pjmlp »

howinteresting wrote: post #449
pjmlp wrote: post #447

Earlier quoted context omitted.

Garbage collected languages also offer means to do C like memory allocation, it is matter to use the language features and FFI capabilities, but many just learn their stacks superficially and follow Rewrite in X trendy blog posts instead.

There is a very big difference between what particular environments offer in theory (yes, you can write object pools in Java and many high-performance projects use them) and the situation in practice (there are people who spend a large chunk of their professional careers doing JVM tuning). Idiomatic Rust avoids the situations which require JVM tuning experts. You can write a Rust service, put it into production and t…

Only when speaking about kernel code, drivers, and similar scenarios.

You are the one focusing in Java, and in your answer proved exactly my point of knowing stacks superficially.

Object pools aren't the only way to reduce memory footprint in Java.

A bit of FFI into host OS syscalls and it is done, or a tiny high performance native library for a custom data structures and ready for the races.

No need to throw away 25 years of tooling and libraries.

Then we can move into languages that offer exactly the same features as C++, like D, Nim, Swift, Eiffel, Ada.

Re: Speed of Rust vs. C

#500

Post by pjmlp »

myrrlyn wrote: post #455
pjmlp wrote: post #316

Earlier quoted context omitted.

They don't enforce the use of transactions, nor exclusive access to database tables.

show me a c program that does this in a manner that a rust program can't emulate

C doesn't advertise fearless concurrency.
Post reply on HN