`wgpu-core` might be able to optimize submission-time validity checks by binning

[jimblandy]

When a command buffer is submitted, wgpu always has to check each and every resource it touches, to see if the resource has been destroyed or invalidated. But these checks are a waste in correct programs, because such programs never actually submit command buffers that refer to bad stuff.

So the supposedly cool idea would be to partition resources into some arbitrary number of bins, and give each bin a "last time anyone destroyed anything in here" timestamp. Destroy methods would update the resource's bin's timestamp.
Command buffers would hold the timestamp of their own creation, and a bitmask of the bins containing the resources they actually refer to.

Then, at submission time, a command buffer would check the timestamps of its resources' bins, and only investigate further if some bin's timestamp was later than its own creation timestamp. If the bin's timestamp is older than the command buffer's, then we know nothing in the bin was destroyed since the command buffer was created.

If there's lots of resource destruction going on, then you'd get a lot of timestamp updates, and this wouldn't really help. But if you don't have much resource destruction going on, then many of the bins will have rarely updated timestamps, and submission checks could just skip them entirely.

You could even group resources into bins using some heuristic that predicted likelihood of destruction. I'll bet most deleted resources are young, for example. So if you assigned bins round-robin style, then all the youngest resources would be concentrated in the bins visited most recently by round-robin.

Sure, you'd have long-lived resources in those bins, too. But the cost of checking them would be amortized:

• If you have the oldsters concentrated in a few bins, you'd only check them when round-robin happened to pass by and throw all the youngsters in the bin with them.

• If you have the oldsters evenly distributed across the bins, then you only have a few oldsters to check on each submission.

There are actually two independent optimizations here:

• Even if command buffers have no bin bitmaps and we check all the bins, as long as resource destruction is rare, being able to skip over the entire bin after a timestamp check is a win.

• Even if resource destruction is common, as long as the bitmaps have a low population, then being able to avoid checking many bins is a win.

In order for this approach to be useless, bitmaps have to have a high population, and bin timestamps need to be frequently new.

Perhaps bindgroups could have bin masks too.

[jimblandy]

Basically, this is Bloom filters, but for invalidation.