News for hackers. Stuff that matters.
Re:Static search trees: 40x faster than binary search by skrebbel on Wednesday January 01, 2025 @08:15AM (#42565820)
Totally off topic, but I've started to notice that more and more algorithmic low-ish level content assumes Rust by default. My entire life I've been used to anything algorithmic being either written in sciency pseudocode (invariably in latex-generated PDFs), or plain old C(++), the vulgar latin of computer programming. I know C and I don't really know Rust but nevertheless I love that this is changing! I'd never advise a new programmer interested in low-level/fast stuff to begin with C now, so much good content is written around Rust.

And, well it doesn't really matter for the core subject. I could follow this post fine even though I don't really know Rust (just like I assume a Rust programmer could follow a well written algorithms deep dive with examples in C with a bit of dedication). So why not standardize on a better language? I like it. I'd love if a bit more Zig was thrown into the mix here but either of them feel like a better default than C at this point to me.

Re:Static search trees: 40x faster than binary search by uecker on Wednesday January 01, 2025 @08:25AM (#42565877)
This assumes that Rust is actually a better language. IMHO it isn't.
Re:Static search trees: 40x faster than binary search by p2detar on Wednesday January 01, 2025 @08:55AM (#42566023)
I’m still unsure of how to feel about Rust. But if it has made it into the Linux Kernel, then I assume adoption is ongoing.

Still, Zig seems somewhat more intuitive to me, even though I’ve used it as little as Rust thus far.

A nice write up on the topic Zig and Rust: https://matklad.github.io/2023/03/26/zig-and-rust.html

edit: typos

Re:Static search trees: 40x faster than binary search by deaddodo on Wednesday January 01, 2025 @02:53PM (#42568741)
Generally Zig is going to be more intuitive for C developers (people who prefer more low-level and procedural style coding), while Rust would be more intuitive/conducive to C++ developers (those who prefer more abstractions and language level features/guarantees).

Which is totally fine, there's a reason C++ never completely subsumed C; both are valid avenues.

Re:Static search trees: 40x faster than binary search by root_sleep on Tuesday January 14, 2025 @05:25PM (#42704797)
Not exactly sure about it myself either. There are things I like about it but at the same time there others that sort of bother me (uncertainty about whether the language will stick around, ugly syntax in certain cases). Being in Linux is impressive for a language, but I suspect most will stick to C.
Re:Static search trees: 40x faster than binary search by 110jawefopiwa on Wednesday January 01, 2025 @10:37AM (#42566633)
I think the main problem is that Rust doesn't allow for basic data structures like graphs or doubly-linked lists without extra effort, which is why I've generally always preferred pseudocode.
Re:Static search trees: 40x faster than binary search by fpoling on Wednesday January 01, 2025 @01:27PM (#42567964)
Well, one can always emulate that in Rust with array indexes. And it will be closer how the actual CPU works where a pointer is just an offset into a memory chunk.

Perhaps this is the reason performance oriented articles prefer Rust. In allows to skip a lot of memory allocation while still catching memory-safety bugs, which is a hard problem with C++.

Re:Static search trees: 40x faster than binary search by szundi on Wednesday January 01, 2025 @03:35PM (#42569078)
How could something to implement a pointer be more straightforward than a pointer? People seem to like Rust in excessive, sometimes botheringly excessive proportions.
Re:Static search trees: 40x faster than binary search by oconnor663 on Thursday January 02, 2025 @11:57PM (#42582591)
I don't think the indexing strategy is more straightforward in general. It's a thing you have to learn, and the fact that you have to learn it is part of Rust's famously steep learning curve. That said, there are some common cases where you might wish you'd used indexes instead of pointers in other languages too:

- Working with resizeable collections like std::vector in any non-GC language, where resizing invalidates pointers.

- Serialization. If your objects contain indexes to each other, it's easy to turn them into e.g. JSON. But if they contain pointers to each other, it's tricky.

Re:Static search trees: 40x faster than binary search by amelius on Wednesday January 01, 2025 @06:42PM (#42570248)
How are you going to garbage collect inside your array? Sounds like you are just evading the problem and reinventing the heap.
Re:Static search trees: 40x faster than binary search by burntsushi on Wednesday January 01, 2025 @10:26PM (#42571330)
Not easily. But not all use cases require it. The regex crate makes heavy use of this pattern for finite machine states, for example. But this fits nicely with an arena allocation pattern, so everything can just be dropped at once.

Despite this, it's one of the fastest regex engines around: https://github.com/BurntSushi/rebar#summary-of-search-time-b...

Here's a related but more isolated analysis: https://github.com/burntsushi/rsc-regexp

Re:Static search trees: 40x faster than binary search by amelius on Thursday January 02, 2025 @10:27AM (#42575241)
You could probably make an even faster regex by JIT-compiling the resulting automaton.
Re:Static search trees: 40x faster than binary search by burntsushi on Thursday January 02, 2025 @11:23AM (#42575806)
The benchmarks I linked include multiple regex engines with JITs.
Re:Static search trees: 40x faster than binary search by oconnor663 on Friday January 03, 2025 @12:47AM (#42582896)
I'm not sure whether this is exactly what you mean, but when you need to support deletions you can switch to a "generational" collection like Slab or SlotMap. Your indexes are still integers, but under the covers some of the bits get repurposed to disambiguate new elements that reuse old slots.
Re:Static search trees: 40x faster than binary search by emilsayahi on Wednesday January 01, 2025 @03:18PM (#42568941)
I often hear this and am confused; not only are things like 'object soup'[0] possible and straightforward (putting things in collections and referring to them by indices), I never concretely hear why a graph or doubly-linked list becomes uniquely difficult to implement in Rust (and would genuinely be curious to learn why you feel this way). If you needed such data structures anyway, they're either in the standard library or in the many libraries ('crates' in Rust-lingo) available on Rust's package registry[1]---using dependencies in Rust is very straightforward & easy.

[0]: https://jacko.io/object_soup.html

[1]: https://crates.io/

Re:Static search trees: 40x faster than binary search by amelius on Wednesday January 01, 2025 @06:26PM (#42570172)
Object soup is like reinventing the heap, badly.
Re:Static search trees: 40x faster than binary search by oconnor663 on Friday January 03, 2025 @12:37AM (#42582840)
I have two different reactions to this:

- From the perspective of e.g. C++, I don't think it's reinventing the heap. We often prefer to use indexes into a std::vector or similar, even when putting everything in std::shared_ptr is an option, because the dense layout of the vector gives us the blazing fast cache performance we crave. It also avoids memory leaks from reference cycles.

- From the perspective of e.g. Python, yeah it's reinventing the heap. Unless you need to serialize the whole collection into JSON or something, it's much less convenient. But (almost) no one uses Rust instead of Python just for the convenience. (There are dozens of us! Dozens!)

Re:Static search trees: 40x faster than binary search by MobiusHorizons on Wednesday January 01, 2025 @09:56PM (#42571180)
One of the reasons to reach for a low level language is to have control over tradeoffs specific to your use case instead of using some pre-packaged option. Data structures are a very good example. Generic data structures like those in the standard library will likely suffice for many use cases, but a low level language must give the user the control to write their own. It’s just table stakes for this type of language.
Re:Static search trees: 40x faster than binary search by rcxdude on Thursday January 02, 2025 @04:19AM (#42572954)
Thankfully, rust does give you that level of control, you can write your own doubly-linked list implementation if you want, and you can pick your safety-overhead tradeoff.
Re:Static search trees: 40x faster than binary search by papichulo2023 on Thursday January 02, 2025 @02:32AM (#42572512)
Not sure about Rust std. But on cpp I heard a lot low-level companies avoid using its standard library since it is too bloated and optimized for too many cases.
Re:Static search trees: 40x faster than binary search by itishappy on Thursday January 02, 2025 @10:29AM (#42575261)
The ownership and model makes working with pointers a lot more complicated, which is the core of a good graph or doubly-linked list datatype.

> Learn Rust With Entirely Too Many Linked Lists

> In this series I will teach you basic and advanced Rust programming entirely by having you implement 6 linked lists. In doing so, you should learn:

* The following pointer types: &, &mut, Box, Rc, Arc, *const, *mut, NonNull(?)

* Ownership, borrowing, inherited mutability, interior mutability, Copy

* All The Keywords: struct, enum, fn, pub, impl, use, ...

* Pattern matching, generics, destructors

* Testing, installing new toolchains, using miri

* Unsafe Rust: raw pointers, aliasing, stacked borrows, UnsafeCell, variance

https://rust-unofficial.github.io/too-many-lists/

Re:Static search trees: 40x faster than binary search by thayne on Wednesday January 01, 2025 @05:54PM (#42569988)
It doesn't though.

Those are fairly straightforward to implement if you are ok using a reference counted type (along with weak references), although that will hurt performance. That would be similar to using a shared_pointer in c++.

And you can implement code similar to what you would in c or c++ if you use raw pointers and unsafe code.

Where you run into difficulties is if you want something that is fast and safe. And then you need a more complicated design that probably involves using indices into a Vec instead of pointers.

Re:Static search trees: 40x faster than binary search by amelius on Wednesday January 01, 2025 @06:25PM (#42570163)
Using a Vec for doubly linked lists sounds like overkill. There's got to be more efficient and more elegant way.
Re:Static search trees: 40x faster than binary search by unrealhoang on Wednesday January 01, 2025 @07:08PM (#42570384)
Yes, there is, just use plain old pointers. Who cares about UB anyway.
Re:Static search trees: 40x faster than binary search by thayne on Thursday January 02, 2025 @04:02AM (#42572862)
Using a Vec actually has some benefits beyond the safety guarantees from rust. There are fewer allocations, and you probably are more likely to get nearby nodes on the same cache line.
Re:Static search trees: 40x faster than binary search by jltsiren on Wednesday January 01, 2025 @10:27AM (#42566561)
I think it's almost irrelevant how good Rust is as a language. Rust is winning in many contexts, because you can use it to replace C++, but the standard library and tools are substantially better.
Re:Static search trees: 40x faster than binary search by nostradumbasp on Wednesday January 01, 2025 @02:52PM (#42568734)
The entire user experience is so much nicer that even if Rust was slightly worse I would prefer it. I don't miss header files, makefiles, not having a package manager, maintaining all the crazy code people wrote themselves as pet projects instead of using an existing project in an ecosystem. Thankfully its not worse, so I don't even have to weigh the odds.
Re:Static search trees: 40x faster than binary search by tomcam on Wednesday January 01, 2025 @05:02PM (#42569689)
Wait isn't cargo a package manager? Not a rust expect so I'm probably missing something
Re:Static search trees: 40x faster than binary search by Tanjreeve on Wednesday January 01, 2025 @05:47PM (#42569953)
I think their point was that Rust has a batteries included package manager (cargo). Another advantage of which being that all rust projects are pretty standard in that particular aspect.
Re:Static search trees: 40x faster than binary search by nostradumbasp on Wednesday January 01, 2025 @07:16PM (#42570421)
That is correct.
Re:Static search trees: 40x faster than binary search by amelius on Wednesday January 01, 2025 @06:23PM (#42570150)
Without makefiles, how do you do projects with multiple languages or code generators like lex and yacc?
Re:Static search trees: 40x faster than binary search by nostradumbasp on Wednesday January 01, 2025 @07:39PM (#42570559)
Well, I don't use makefiles to deploy software with Rust. I also have never used lex or yacc, but I bet there are similar tools in the ecosystem, or wrappers for those. That would obviate what I will offer below.

Often a new language in a project would define an application boundary. So those would be different containers or services. I may deploy via container images, or an OS specific installer, etc. If we aren't crossing an application boundary I may use FFI. Sometimes I use https://rust-lang.github.io/rust-bindgen/ to smooth that over for C dependencies. There is also a nice concept called a build.rs file: https://doc.rust-lang.org/cargo/reference/build-script-examp.... There's also tools like: https://github.com/casey/just and https://sagiegurari.github.io/cargo-make/

I rarely use multiple languages with Rust. A lot of interpreted languages have bindings through crates and can go in to a project through Cargo. If it involves JS/TS on desktop, I'm usually using Tauri for that. Guess it depends on the system?

Hopefully that helps. You can also still use a Makefile if you want I just haven't dealt with one in a long time.

Re:Static search trees: 40x faster than binary search by eslaught on Wednesday January 01, 2025 @08:21PM (#42570786)
If you're embedding, say, a C library inside of Rust, you can do so via a so-called "build.rs" script [1]. These run at build time so you can do pretty much whatever you want. They're not necessarily pretty, but given that Cargo isn't going to support other languages natively, it's often a less-evil option.

Then there are build systems that natively support Rust in addition to other languages and know how to plug them together [2] [3] [4]. If you're already using one of these existing tools, then you don't need to roll your own, you can plug it into your existing project.

Of course if you really are using Makefiles in C you're already living in the wild west, so it's on you to figure out how to add Rust to your projects in that case (or switch to a better build system).

[1]: https://doc.rust-lang.org/cargo/reference/build-scripts.html

[2]: https://bazelbuild.github.io/rules_rust/

[3]: https://buck.build/rule/rust_library.html

[4]: https://mesonbuild.com/Rust.html

Re:Static search trees: 40x faster than binary search by richrichie on Thursday January 02, 2025 @02:02AM (#42572384)
Rust is great for pet projects. Otherwise, it is a big security risk for large commercial projects, since it lacks a useful standard library and any non trivial program needs to download a thousand crates to work.
Re:Static search trees: 40x faster than binary search by alfiedotwtf on Thursday January 02, 2025 @07:49AM (#42573973)
What languages are you thinking of that have all the libraries you could ever possibly need for a commercial project built-in?
Re:Static search trees: 40x faster than binary search by richrichie on Thursday January 02, 2025 @09:08AM (#42574529)
Go and C++ have pretty decent standard libraries, for example.
Re:Static search trees: 40x faster than binary search by alfiedotwtf on Friday January 03, 2025 @09:50AM (#42586090)
Apart from `simd`, and if you allow us to embelish by using Tokio and I'll ignore the C++'s reliance on Boost, there's not really much I can see from C++'s standard library that's anyhow wildly different from Rust.

What in particular do you see lacking in Rust that you can do in C++?

Re:Static search trees: 40x faster than binary search by uecker on Friday January 03, 2025 @04:05PM (#42589456)
Also from legal and liability point of view it opens a can of worms.
Re:Static search trees: 40x faster than binary search by alightsoul on Monday January 06, 2025 @11:01AM (#42611653)
Yeah. Too much stuff to manage
Re:Static search trees: 40x faster than binary search by nipah on Monday January 06, 2025 @10:41AM (#42611463)
This is pure bs considering the massive amount of large commercial projects written in C# that depends on a lot of community-made packages.
Re:Static search trees: 40x faster than binary search by alightsoul on Monday January 06, 2025 @11:00AM (#42611645)
C# and other high level languages like Java are much safer than any low level language including Rust, in those languages you don't even have an unsafe mode
Re:Static search trees: 40x faster than binary search by neonsunset on Monday January 06, 2025 @01:46PM (#42613810)
.NET languages have always had access to unsafe feature subsets at multiple levels of abstraction with varying degrees of "unsafety". .NET has also been slowly leaning more into its systems-programming side. It is now at a strange crossroads where it is not like C or C++, or as a much better replacement, Rust but not like Java or Go either.
Re:Static search trees: 40x faster than binary search by debrutal on Monday January 06, 2025 @02:25PM (#42614425)
Have you ever heard of Java native Interface or Java native abstractions? Thats unsafe AF. Same goes for native implementations. Whenever something needs to be done fast, the jvm implements native code. Have you ever debugged that magic bs? Guess why people chose a high level language, because they don't want to bother with complicated stuff. Still those abstractions on these languages are not better, even worse considering their APIs, than rusts. Working with thread locals or synchronized keywords, non atomic members and all the bad concurrency mechanisms inside Java is unsafe shy default.

Runtime exceptions is what I consider a bad practice and it's spread everywhere in Java... Also the language evolutions are not really that good. So bringing errors/exception to the compilation time is a safety net.

Despite the fact that languages with managed memory safety bring a lot of potential for abusively high memory consumption, random GC stop the world situations and worse like oom.

Whenever I had to analyze a memory issue with an application it was no fun at all, despite the challenge.

The jvm specifications are so flawed considering security... Creating classes at runtime from a stream using reflections, which is totally spec compliant gave us log4shell. Why even load serialized classes from remote?! Fail by design.

So safety is still context sensitive and depends on the requirements. If you write bad software you can ignore some of the mentioned aspects, though it still lacks of 'security'

Just my 2 cents here

Re:Static search trees: 40x faster than binary search by nipah on Tuesday January 07, 2025 @12:37PM (#42625053)
C# absolutely have an unsafe mode, basically since version 1. You can use pointers, deal with stackallocated memory and all of that, in recent versions you can even natively allocate and deallocate memory using the `NativeMemory` type. Of course, it is harder to cause problems and the `unsafe` isolated areas provide a similar unsafety abstraction mechanism as Rust does, but it is still possible. And in the edge, both C# and Java have FFI and can call directly into C/C++ (or basically any native language) code, so you can still open a big security hole in your application (and nuget makes it very convenient to even ship native binaries in your packages, as you can see with the many wrappers around things like libsodium, raylib, windows/linux API's and more).

In the end of the day, C# had the same ideas of isolating unsafety that Rust has, and provides many safe wrappers around good libs, like Skia (SkiaSharp, very famous and widely used) for example. So those ideas are kinda market proven as well.

Re:Static search trees: 40x faster than binary search by norman784 on Wednesday January 01, 2025 @08:53AM (#42566017)
I would argue that in some sense it is, just because of the enforced safety and correctness.
Re:Static search trees: 40x faster than binary search by peoplefromibiza on Wednesday January 01, 2025 @09:07AM (#42566094)
So it's Ada since 1980, before C++ was even created.
Re:Static search trees: 40x faster than binary search by sroussey on Wednesday January 01, 2025 @11:05AM (#42566850)
I wrote my first optimizing compiler for Ada in C++ around 1990.
Re:Static search trees: 40x faster than binary search by uecker on Wednesday January 01, 2025 @05:13PM (#42569760)
It does neither enforce correctness nor safety. It enforces memory safety in programs that stick to the safe subset. But don't get me wrong, Rust certainly has many good ideas and the focus on memory safety is good. I still do not think it is a great language.
Re:Static search trees: 40x faster than binary search by matt3210 on Thursday January 02, 2025 @12:22AM (#42571899)
The problem with rust is that it’s has lots of features but isn’t c like. Python doesn’t have much syntax so it’s fine to be not c like but rust has 100% new syntax and a lot of syntax with respect to c. I can pick up c like languages easy but rust just makes me mad to look at.
Re:Static search trees: 40x faster than binary search by Narew on Wednesday January 01, 2025 @09:46AM (#42566282)
I don't know if it's good or bad, with pseudo code you put no constraints on how it should be implemented. It's known that some kind of algorithm are really hard to implement in Rust (every one use the link list data structure as an exemple). So having the article that use rust is good to see it can fit to rust constraints but at the same time does this constraint limit the algorithm itself ?
Re:Static search trees: 40x faster than binary search by curiouscoding on Wednesday January 01, 2025 @10:36AM (#42566625)
Anything in particular that threw you off? I'd be happy to add a few words to briefly explain some of the less intuitive rust syntax.
Re:Static search trees: 40x faster than binary search by skrebbel on Wednesday January 01, 2025 @10:47AM (#42566702)
Nah just the final bits, stuff like `Simd::<u32, 8>::splat(q)`, I'm not sure what splatting is or how Rust's Simd library works or, admittedly, how SIMD works in detail at all. So eg I'm not sure what that 8 is doing there in the type parameters, details like that. Maybe this isn't a Rust thing but a SIMD thing, btw, I don't know much Rust but I also never wrote any SIMD code ever. I don't know how the article could be clearer, IMO once you go into the deep nitty gritty optimization stuff you just gotta assume the reader knows the tools you're using. I'm OK with dropping out halfway cause the core idea is there even before you squeeze out all the perf.
Re:Static search trees: 40x faster than binary search by burntsushi on Wednesday January 01, 2025 @11:13AM (#42566912)
`Simd::<u32, 8>` is describing a vector with 8 lanes, where the width of each lane is 32-bits. For targets that support it, that should get you a 256-bit register.

The `splat(q)` constructor is just saying, "populate each lane with `q`." That is, the value is "splatted" across every lane in the vector.

The main idea of SIMD is simple: you represent multiple points of data in the same register and use specialized CPU instructions to operate on those points simultaneously. The difficulty of SIMD is coming up with clever algorithms that use the available instructions in an efficient way.

Re:Static search trees: 40x faster than binary search by skrebbel on Wednesday January 01, 2025 @11:49AM (#42567177)
Ahh right, I've been doing too much TypeScript lately. I thought a type parameter couldn't impact behavior but only typechecking but clearly in Rust (like in C++) it can. Thanks for the explanation!

Ah so splat is like a memset for the entire vector to the same value. OK makes sense, I bet that wasn't actually a Rust-ism at all, just basic SIMD lingo I didn't know. Thanks again!

Re:Static search trees: 40x faster than binary search by shawn_w on Wednesday January 01, 2025 @11:30PM (#42571640)
It's the Intel intrinsic `_mm256_set1_epi32()` except with an amusing name. Got to give Rust the win here.
Re:Static search trees: 40x faster than binary search by skrebbel on Thursday January 02, 2025 @03:08PM (#42578265)
wow yeah, i way prefer Rust's notation there! but i assume you could make a similar zero-cost abstraction with some mildly crazy C++ template programming.
Re:Static search trees: 40x faster than binary search by bennythomsson on Wednesday January 01, 2025 @12:03PM (#42567308)
Nice to see other real experts (and a bit of celebrities) in here.

(For the uninitiated: Burntsushi of ripgrep fame.)

Re:Static search trees: 40x faster than binary search by skrebbel on Wednesday January 01, 2025 @12:54PM (#42567700)
yeah tbh i was a bit starstruck that burntsushi would reply to my comment explaining what i assume is utter SIMD basics. that must be how swifties feel when she (or, likelier, her PR drones) click "like" on their insta comments.
Re:Static search trees: 40x faster than binary search by freeopinion on Wednesday January 01, 2025 @04:44PM (#42569577)
Does burntsushi have PR drones (who can explain SIMD)? :)
Re:Static search trees: 40x faster than binary search by npalli on Wednesday January 01, 2025 @11:00AM (#42566804)
Quite honestly, doesn't seem like Rust is a win here over C++. In fact, C++ has fewer sigils that make it somewhat easier to read sort of striking the balance between being simple enough (C-like) and abstractions (templates). Readability wise, I would have preferred Julia as that would have been the cleanest explanation of the code through the different topics at sufficient level of detail. Alas, it seems to have stalled somewhat (relatively speaking). It also doesn't help that every Rust article has Rust advocates jumping on you with "WAHT ABOUT SAFETY" which is off-putting since not every program needs to deal with all the complexity of the Rust memory/lifetime model to enable safety (simple bounds checking etc. might be sufficient).
Re:Static search trees: 40x faster than binary search by fpoling on Wednesday January 01, 2025 @01:36PM (#42568047)
The article is about how to squeeze absolute maximum in performance from the hardware. So you need a language that allows a relatively low-level access to hardware. And big plus of Rust is that it has standard SIMD libraries while C++ will get them only in C++26
Re:Static search trees: 40x faster than binary search by User23 on Wednesday January 01, 2025 @11:13AM (#42566915)
Fun fact: a lot of that “sciency pseudocode” is actually Algol.
Re:Static search trees: 40x faster than binary search by mananaysiempre on Wednesday January 01, 2025 @03:31PM (#42569054)
Because that’s the original problem statement for Algol! As in, we’ve been publishing all that pseudocode for quite a bit and it seems like conventions have emerged, let’s formalize them and program in that. ... People were markedly more naïve back then, but then that’s sometimes what it takes.
Re:Static search trees: 40x faster than binary search by EGreg on Wednesday January 01, 2025 @08:15PM (#42570754)
And I thought it would be python?

Scientific stuff (scipy) and now all the ML stuff too