New week, new Rust! What are you folks up to?
I'm working on apis-saltans.
Improving performance of my GPU-based physics simulation. Since my previous post, a lot of time has passed and a lot has changed. Now my sim has collisions, parameters configurable via env vars, performance is much better, the code is cleaner, and README is actually useful.
I decided to focus on performance instead of features, because there is still a lot of relatively low hanging fruit. For example, in the past 2 days, I managed to improve performance by 40% just by replacing a shader with a hardware supported buffer clear command (-225 lines of code) and implementing a few easy optimizations. Now it can comfortably simulate 256k particles on Radeon RX 560 at 30 FPS, and I suspect that a million might be possible.
So that's what I'm doing this week — squeezing everything I can from my RX 560.
I am thinking about this. I expect it is a "well-known" technique, does anyone know?
==
Idea for splitting hash buckets incrementally.
Suppose we have a hash table with 4 buckets, numbered as below:
[2] [6] [3] [4]
0 1 2 3
and suppose that bucket [6] ( index 1 ) is "full" and we want to insert into it.
We first double the number of buckets:
[2] [2] [6] [6] [3] [3] [4] [4]
0 1 2 3 4 5 6 7
without creating any new pages. This is a relatively cheap operation.
Now we split the records in [6] (now index 2 and 3) into two, the new page id being [7], as below:
[2] [2] [6] [7] [3] [3] [4] [4]
0 1 2 3 4 5 6 7
[6] and [7] should each be roughly half-full, and we can continue inserting.
Now suppose later on [3] ( index 5 ) is full and we want to insert into it.
We first check the "buddy"*, index 4. If it has the same page number ( as is the case here ),
we do not need to double the number of buckets, instead split the records in [3] into two
buckets ( new page number is [8] ), as below:
[2] [2] [6] [7] [3] [8] [4] [4]
[3] and [8] should each be roughly half-full, and we can continue inserting.
The buddy position is x+1 if x is even, x-1 if x is odd.
Upgrading crates from Ureq 2 to Ureq 3, dealing with breaking changes.
Next, upgrading crates from WGPU 24 to WGPU 30, dealing with breaking changes.
The game is similar to chess in terms of algorithms, but the rules are simpler. For the standard 7 columns x 6 rows board size, the game tree has 4.53 * 10**12 legal positions - which is not tiny, but much smaller than chess and small enough that it can be solved exactly.
rv32i+ emulator, currently cleaning up my repo and building some test-benches for it
having to work around the lack of global_allocator is a pain right about now
Pondering whether I should replace BTreeSet in my parser generator.
I used that structure for relatively small sets (or maps) when I needed a sorted output and a repeatable outcome. Then I realized the search was linear, something that was too easy to miss in the documentation! I'm not entirely sure why a b-tree search implementation would be linear, and even less why it's like that in the standard library, but it explains the performance drop for sets containing more than a few items.
I tried to find an alternative, but the few I've tested had significantly lower performances (e.g. indexset::BTreeSet, btree_indexmap::BTreeIndexSet, ...): more than 200% slower (a x3 factor!) for from_iter() and respectively 70% and 44% slower for contains(). Most crates are still version 0.x, though, and many have been abandoned quickly. And now there's also AI slop to filter out.
For the LR parser construction, it helps to use b-trees, but I'll probably have to take another approach because their size can grow more than where I was using it before. Maybe a combination of HashSet, Vec and quick sort. That, or I accept to get side-tracked and create a small structure just for my needs, and no guarantee of performance gain without enough effort.
I think you (reasonably) misread this documentation:
A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array.
[...]
Currently, our implementation simply performs naive linear search. [...] Using linear search, searching for a random element is expected to take B * log(n) comparisons, which is generally worse than a BST. In practice, however, performance is excellent.
How I read this is that searching the elements in each node is linear, which contributes a constant factor (B), but the overall algorithm is logarithmic. Currently it looks like B is 6, whatever that's worth (not guaranteed to stay that way).
Yes, I did express it quite badly, sorry.
Creating high performance channel as must as I can eventhough I am still learning, that I will use it to replace Flume in my logger :v for now it is already massively higher performance than Flume, STD channel (Crossbeam). I still improving as much as I can, currently I'm trying to figure out why using pure yield has better performance than hybrid backoff (spin -> yield -> then park), I'm trying to make the hybrid backoff has higher performance than only yield, because why Crossbeam use that backoff style, it may has pros than pure yield, I'm trying to find it :>
pstd::BTreeMap (my crate) uses binary search to search the "small" nodes. There isn't much in it. I think I use a larger elements per node by default, it also allows that to be configured.
Edit: yes, the default branch is 64:
Thanks, that's interesting!
I suppose it's the matter of finding the soft spot depending on how the B-map is used.
Looking back at that, something I didn't realise at the time is most ( well all that I know of ) memory allocators allocate only in sizes that are powers of two. So increasing the node size by less than a doubling is a "mistake". I could re-visit it.
That's something I've been wondering about the standard library's B = 6 (B-1 to 2*B-1 items), but I haven't dissected the whole code; it's not really straightforward due to optimizations and so on.
There might also be a potential mismatch between the optimal value for the allocation system and the optimal one for the performances... Nothing is simple.
Usual problem. wgpu, winit, egui, and wgpu-profiler all have version dependencies, and they're out of sync again. wgpu-profiler hasn't caught up to wgpu's latest version yet.
I've been cleaning up some old code and experimenting with a few Rust features I hadn't used before. Hoping to wrap up a small side project by the end of the week if everything goes smoothly.