Comment by Const-me | Hacker News Reader

Comment by Const-me | Hacker News Reader

Parent Full thread

> Why compose classes, abstract base classes, etc. when you can compose simple functions

For some kind of projects (video games, applied math, anything else that is sufficiently performance or latency sensitive), data structures are just as important as code. And they need to be composed, too.

For example, in C++ I can put small structures into couple megabyte-sized vectors, because memory controllers love sequential RAM access. Then I put these vectors in another vector, because address space might be fragmented and memory manager might not be able to give me continuous 1GB buffer, also to save CPU time + RAM bandwidth when growing my dataset to gigabytes. Then I wrap these vectors into another container that creates and maintains an index over the whole dataset using a hash map, because besides sequential access, other times I want to lookup my values by some key, and I want the lookups to run fast. And so on.

FP paradigm is just fine for composing functions. AFAIK, FP offers little for composing data structures. And those sophisticated specialized data structures are often the key for writing high-performance code.

There are libraries like https://hackage.haskell.org/package/repa that make some of these tasks much easier to do. (Write your program/algorithm in terms of these arrays and all operations on them are seamlessly parallelized.) And there's really no reason you can't wrap something by making a new data type that includes the original arrays and an index.. it's just not a class.

While it's worth mentioning that Haskell does allow you to get pretty low level, it nonetheless has a GC, and the code you end up writing often looks more like C than FP. Rust is a great alternative that combines a lot of the raw performance and control over memory of C/C++ and good stuff from FP (e.g. sum types/pattern matching.) (Or even better, use something like Haskell and FFI with Rust for performance-critical parts.)

I never used Rust in commercial projects. But to my knowledge, data structures in Rust are not exceptionally good at composing, because the language lacks raw pointers.

In C++ I can add hashmap-based index to existing collection of values without duplicating the values, because I can only keep pointers in the map. I can add linked list-based LRU tracking to existing collection of values. I can use pointers to implement graph-based structures. While there’re workarounds in Rust, such as reference counted pointers, raw pointers in C and C++ are just faster.

> the language lacks raw pointers.

This is incorrect, Rust has raw pointers. Those reference-counted pointers that you mention are all just standard library types implemented using raw pointers under the hood.

I’m sure Rust smart pointers are implemented using traditional C pointers.

Regardless of how you call them, you still can’t use them to compose data structures into higher-level structures in Rust.

In C++ with raw pointers, I can combine a hashmap with an existing collection of values to speed up lookups, without duplicating values. I can combine hash map with linked list to create an efficient LRU cache, with a few lines of my own code.

C++ can do that because collections, std::unordered_map, std::list and the rest of them, expose raw pointers at their API boundaries. It’s possible to store these pointers in other collections, encapsulating one or more simple data structures into a higher-level specialized data structure, with the performance characteristics suitable for the job.

A star-const T or star-mut T (wow I cannot figure out HN's formatting here) in Rust does absolutely everything a C pointer can. They're the same thing. You can do all the stuff you're talking about here. Exposing a safe interface does not also mean not exposing an unsafe one as well for these kinds of things.

Technically, yes I can.

However, look at the Rust implementation of the LRU cache: https://github.com/contain-rs/linked-hash-map/blob/master/sr...

See how much code is there (more than 1k lines), and note most code is unsafe.

In C++, one would probably use list<pair<K,V>> for storage, together with unordered_map<K, list<pair<K,V>>::iterator> for indexing. And the implementation would be trivial, because there’s no need to re-implement a linked list, you only need to implement these get/set methods that update both collections at the same time.

In Rust however, they had to come up with their own implementation of linked list. The LinkedList from standard library doesn’t expose raw node pointers in the API, therefore it can’t be used for the job.

Sure, but that's an oversight of the LinkedList API (which, honestly, was almost removed from std all-together, it's not exactly a shining beacon of API design) than some sort of inherent limitation of smart pointers, which seems to be what you're saying here.

I don’t think that was an oversight.

I think rust safety model prevents rust containers from returning mutable pointers to the contained items. Especially pointers to item's implementation details, like nodes of that linked lists.

And without raw pointers to items, you can’t easily compose containers to make higher-level data structures from them.

https://doc.rust-lang.org/stable/std/vec/struct.Vec.html#met...

(That is, many data structure _do_ do this, and you _can_ do it. It is an oversight.)

There is no reason why you couldn't "compose data structures" in FP. Lists are composed data structures, as are trees. And Haskell's type classes are in fact a superior way to build ADTs.

The difference is the mindset. FP makes it really easy to compose higher-level functions. But composing higher level functions typically means little control where the intermediate results are stored (which is what Game developers need).

You can absolutely write C++ style in Haskell by composing imperative functions (e.g. IO monad). The only problem I see is the syntax. There is no built-in syntax for indexing and assignment. Writing

    do
        v1 <- readArray a i
        v2 <- readArray a (i+1)
        writeArray a (i+2) (v1+v2+1)

instead of

    a[i+2] = a[i] + a[i+1] + 1;

gets old really quickly.

> composing higher level functions typically means little control where the intermediate results are stored

Exactly.

I need my code to access sequential RAM addresses as much as possible, because performance.

And sometimes my RAM layout is fixed, because I’m directly sending large sequential blocks of RAM to GPU (e.g. on Windows, by calling ID3D11Device::CreateBuffer or ID3D11DeviceContext::UpdateSubresource), and GPU can only consume C-array of POD types with very specific alignment and padding requirements.

Use the right tool for the job. If the job requires precise control of memory, FP is not the right tool. If the job requires precise control of sequence, FP not the right tool. (Yes, it's a tool that could be made to work, but you're fighting the tool rather than working with it.) If the job requires precise control of timing, lazy languages are the wrong tool.

This does not mean that there is anything wrong with FP or with lazy languages. They're just not the right tool for all purposes. When they're not the right tool, don't use them for that.

Reply on news.ycombinator.com