Enable cache Optimization

[malik672]

Describe the feature

ref: #12842 (comment)
ref: #12842

The main reason this consumes so much storage or allocation I should say is because it's way too cache unoptimized, the whole fetcher.rs seems like it's not taking advantage of the cache instead there are more reads to the main memory instead, a common example should be

1. Hash lookups that are not needed (this might seem efficient with 0(1) constant time indexing but it's not)
2. Hash set with maximum size of 8 should be replaced with a Vec, of course this might not seem logical for indexing but for small data structure it's all about being contiguous in memory
3. Scattered memory access, this leads to more cache miss

in all the reason for such allocation and latency is just because we are not using the cache efficiently,

@hai-rise @mattsse

Additional context

I don't think any amount of code removal or algorithmic reduction will make this more efficient apart from the using the cache efficiently

[hai-rise]

I'm not following the bigger context but CPU cache misses "only" re-fetch values from RAM to CPU without allocating more, while my referenced comment focused on aggressive memory allocations, which is not necessarily related.

I don't think any amount of code removal or algorithmic reduction will make this more efficient apart from the using the cache efficiently

I'm unfamiliar with this specific module, but this statement is generally off:

• The main selling of CPU caches is that reading from memory is very slow. If reading from memory is slow then more complicated operations like allocations, deallocations, or moving data in memory are even slower.
• I've heard several engineers sell 100~1000x speedup for efficient CPU caches but never saw such scale in practice or realistic benchmarks. Meanwhile, I've seen countless scenarios where non-contiguous O(logN) smokes contiguous O(N).

My point is that while efficient CPU caches are always desired, they shouldn't devalue other critical aspects like efficient data structures and memory (de)allocations. They are not mutually exclusive!

[malik672]

you are wrong, they are related actually very very related

1. Think of Cache hits as batching

I've heard several engineers sell 100~1000x speedup for efficient CPU caches but never saw such scale in practice or realistic benchmarks. Meanwhile, I've seen countless scenarios where non-contiguous O(logN) smokes contiguous O(N).

This is technically right/wrong depending on the length of the data structure, so I can't really say, but from what i saw the data structure length was 8 and a hash set was used, made no sense to me tbh, for a larger size a non contiguous is better at the end of the day it's all about the size

My point is that while efficient CPU caches are always desired, they shouldn't devalue other critical aspects like efficient data structures and memory (de)allocations. They are not mutually exclusive!
This again is wrong; you can draw a straight line from cache hits to efficient data structure hence to memory de(allocations)

[malik672]

My point is that while efficient CPU caches are always desired, they shouldn't devalue other critical aspects like efficient data structures and memory (de)allocations. They are not mutually exclusive!

They are very very very very very very very very very very very very very mutually exclusive

[hai-rise]

Nah, let's look at a simple example of Vec<CachePadded<Data>> that tries to get the best of CPU caches:

• Vec puts all the Datas next to each other in memory so iterating them is CPU cache-efficient.
• Each Data is CachePadded to fit a CPU cache line, so a CPU (running a thread) writing to an element wouldn't invalidate adjacent elements in the cache line of other CPUs.

This is not mutually exclusive to efficient memory (de)allocations as one can do efficient pre-allocations with with_capacity and reserve, use clear to reuse allocated memory instead of std::mem::take, etc. On the other hand, a push over the capacity would allocate and move the Vec per push. How much to pre-allocate to avoid this deadly cost depends on the problem at hand and has nothing to do with CPU cache.

This is not mutually exclusive to efficient data structures as when Data is ordered one would need to iterate the whole Vec to find the biggest element. When the number of elements is big, a tree implementation with sloppy memory alignment and no efficient pre-allocation would still beat Vec.

Your argument is that engineers and programs only need to focus on CPU cache and don't even need to care for other things like data structures, memory allocators, or the actual problem and data size a module is solving. I cannot find any context where this makes sense, unfortunately.

A more productive approach would be to propose clear design and code changes that address the actual problem in #12842. "Enable cache optimization" is as unclear as "enable CPU optimization" and "require fewer computer operations". And with any performance work, profiling data and benchmark numbers are more helpful than pure theory always, so the issue would be more convincing if you have them.

[malik672]

Your argument is that engineers and programs only need to focus on CPU cache and don't even need to care for other things like data structures, memory allocators, or the actual problem and data size a module is solving. I cannot find any context where this makes sense, unfortunately

I never said this caring for the cache is the same (in a way) as caring for data structures, memory allocators, they are inter dependent on each other, you can draw a straight line between them: Efficient data structure for small length -> cache efficiency and minimal memory allocation

This is not mutually exclusive to efficient data structures as when Data is ordered one would need to iterate the whole Vec to find the biggest element. When the number of elements is big, a tree implementation with sloppy memory alignment and no efficient pre-allocation would still beat Vec.

I said this previously, using an example I saw in the code: This is technically right/wrong depending on the length of the data structure, so I can't really say, but from what I saw the data structure length was 8 and a hash set was used, made no sense to me tbh, for a larger size a non contiguous is better at the end of the day it's all about the size

A more productive approach would be to propose clear design and code changes that address the actual problem in #12842. "Enable cache optimization" is as unclear as "enable CPU optimization" and "require fewer computer operations". And with any performance work, profiling data and benchmark numbers are more helpful than pure theory always, so the issue would be more convincing if you have them.

I agree, benchmark is always better than theory, my theory is just me observing the code and changing some parts in it, would love to do that fully but I don't really have the time

[hai-rise]

they are inter dependent on each other, you can draw a straight line between them: Efficient data structure for small length -> cache efficiency and minimal memory allocation

My simple Vec example disputed this. For this same "efficient data structure for small length" that you claimed, one would allocate only once if they know the capacity at construction time. If not, one may need to allocate per push. This difference between O(1) and O(n) (not even counting the cost of moving the Vec) depends on whether we know the expected capacity which is tied to the problem at hand and has nothing to do with CPU caches.

My referenced screenshot showed allocations at 100 MB/s with an average lifetime of only 25.77 μs. This is unhealthy, and likely related to (pre)allocating or cloning more than needed regardless of whether the underlying data are contiguous in memory.

My whole points in this thread can be summarized as:

• Performance contributions should either be obvious (removing an unneeded clone, allocation, etc.), or
• Be paired with profiling data or benchmarks to back a claim or proposal, and
• Ideally, be very actionable.

I'm writing this many words because I like your energy (in both Reth and our pevm), but you seem to have a habit of underplaying the challenge of performance works (like over-sticking to a single assumption instead of looking at the bigger picture) and have a rather low issue & PR conversion rate. A change in approach may help you improve at performance tuning, see more of your ideas merged, and all these open-source projects get better :).

[gakonst]

@malik672 i think it's worth understanding Hai's broad point -- don't do crazy optimizations, always profile

[malik672]

@malik672 i think it's worth understanding Hai's broad point -- don't do crazy optimizations, always profile

But I agreed to this ...... :) :)

[malik672]

My simple Vec example disputed this. For this same "efficient data structure for small length" that you claimed, one would allocate only once if they know the capacity at construction time. If not, one may need to allocate per push. This difference between O(1) and O(n) (not even counting the cost of moving the Vec) depends on whether we know the expected capacity which is tied to the problem at hand and has nothing to do with CPU caches.

if we have an estimate, it's good enough, in the code it was 8, at worst it should be +5 that's still good for a Vec,
I definitely do agree with some of your points (especially the benchmark part) I just refuse to agree they cache is not inter dependent on memory allocation/deallocation

I would try to do a pr with benchmark, not sure I've the time but I would try

[hai-rise]

Nice. Some profiling data with Cachegrind to confirm the cache issue or benchmarks to show your solution is better would be very helpful. And feel free to continue in #13219 for collaboration with @Elvis339 in a more focused context 🙏.