I like SIMD, but before super-optimizing your code with SIMD and the like, really consider your data structures and access patterns.

I've been singing Data-Oriented Design's praises, so I'll just collect all my comments here [1], but I think it's a good approach to optimization. I played around with SIMD in my old code (in Zig), but my approach to modelling datastructures was so antithetical to optimization, it was like putting high-performance racing tires on a lemon with a broken engine.

It was the root-of-all-evil-type-premature-optimization, because I wasn't measuring performance, and I wasn't thinking about where the allocations were, etc. Now, I try to model my data as if it were SQL tables, see what my potential "primary keys" could be, and build my data structures around my access patterns.

For example, I used to model trees as structs pointing to other structs on the heap:

    struct Tree {
        tag: TreeTag,
        children: Vec<&Tree>
    }

Now my tree has all the bad characteristics of a linked list (* n nodes * m children), all the fragmentation of multiple heap vectors (* n nodes), and terrible set-up / tear-down time (in this case, Drop alone was taking up a good chunk of runtime).

But a tree can be represented a million ways, and can always be linearized. So now I really consider my access/insert patterns of the tree, whether it's really a tree or some other sort of graph, whether I can store it in a Vec or a Struct of Vecs, etc. Since really looking at things through their access patterns and "primary keys", my code has been much faster and simpler.

This has the added effect that a lot of your data ends up in homogeneous arrays / vecs, which means that the compiler can do its SIMD magic, the CPU can read it from your L1 cache a million times faster, etc. And then when you need to drop down into SIMD yourself, you can write some awesome branchless code.

1. https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

▲ tarnith 8 hours ago | parent | next [-]

Yeah, data layout/cache aware layouts are really key if you really want to unlock making something that ends up in a hot loop fast with SIMD.

Also, avoiding allocations or vtable lookups or a lot of indirection in the part of the code that's actually "hot" is really important. Vectors (in C++) at least aren't necessarily the best fit either, if you end up doing anything that can call an allocation unexpectedly.

▲

Rendello 8 hours ago | parent [-]

> Vectors (in C++) at least aren't necessarily the best fit either

I'm not sure if you use a different allocation strategy or if you're advocating allocating as much as possible up-front, but I'm curious if you have any thoughts on this:

I always end up using (Rust) vectors despite looking at a bunch of slab/arena allocation libraries. Preferably I'd know how much memory I need up front, but barring that I see three options for any allocation that needs to grow:

- Fail;

- Reallocate; or

- Put the overflow in a new allocation, keeping track of where all the "pages" are internally.

In 2, you can't use references/slices (anything with a pointer) because the potential reallocation invalidates those. In 3, it seems ideal because references can stay stable, but you wouldn't be able to have any array-like data cross the "page" barrier as the pointer jump would not be stable. (Although, am I correct in thinking the OS does something like this, and that's why pointer addresses are virtual?).

So, you can't really internally reference data in this sort of context by reference/pointer, it's preferable to use an integer index. In that case, what's the point of the allocator libraries at all? Your standard Vector would have the same reallocation/access characteristics, and you can set a reasonable initial capacity to try and avoid reallocations.

	▲	speedstyle 3 hours ago \| parent [-]
		To your virtual memory comment, the kernel can only do as it's told, but allocators can indeed tell it to shuffle pages around in virtual memory. On Linux that's `mremap` [0], and `realloc` implementations [1] use it for large enough Vecs (apparently 128kiB for glibc and musl). macOS' libmalloc will try to map new pages that extend large allocations in-place, but memcpy elsewhere if existing virtual mappings are in the way. I don't think Windows' HeapReAlloc does either, but they might reserve a larger virtual region and incrementally commit it or something to similar effect. [0] https://man7.org/linux/man-pages/man2/mremap.2.html [1] https://git.musl-libc.org/cgit/musl/tree/src/malloc/mallocng...

▲ luaKmua 3 hours ago | parent | prev | next [-]

This is my eternal battle as a perf engineer. Performance starts with architecture and you can only squeeze so much out a hotpath with poor data layout.

The nice part is that data-oriented code almost always easily supports threading and SIMD.

	▲	saagarjha an hour ago \| parent [-]
		On the flip side a lot of my work as a performance engineer is undoing bad abstractions made by people who read a two blog posts about SoA and decide that encapsulation is stupid

▲ Scene_Cast2 2 hours ago | parent | prev | next [-]

Very much agreed. Even more basic than that - memory access patterns are important. The amusing thing is that you end up writing GPU-style code even for CPU. For example - instead of an array of objects, using parquet-style object of arrays is one such trick.

	▲	Rendello 25 minutes ago \| parent [-]
		There's been some good implicit/explicit discussion about SoA on this post [1]. For anyone curious, there are a few different terms that refer to basically the same thing: - Struct of Arrays (SoA) vs Array of Structs (AoS); - Row-major order vs column-major order; and - Row-based vs column based / columnar (in databases) Most code has arrays of structs (or "lists of objects", the effect is the same), and most databases are row based (same thing). But many game engines use SoA and keep heterogeneous elements together. Some databases like DuckDB do this too, this is an article about the pros and cons of columnar storage in DBs [2]. 1. https://news.ycombinator.com/item?id=49012056 2. https://motherduck.com/learn/columnar-storage-guide/

▲ groundzeros2015 6 hours ago | parent | prev [-]

This. Tables are an efficient implementation of general graphs. It’s the best one I know of (unless your graph can be specialized).