AssetCache: correctness and potential optimization opportunities

[ghost]

AssetCache introduction

AssetCache is one of the core storage abstractions which a piece of data can be persisted into. Note the word "Asset" has no relation to the "Asset Pipeline", because this asset cache can store anything, including the handle to the GPU instance, an HTTP client, and so on. Accessing this cache is going to happen frequently enough that it is worth considering more efficient solutions.

To load something into the cache, one needs to create a type that implements SyncAssetKey or AsyncAssetKey trait. This trait implements the interface to the cache. To form the actual key, these traits assume that the type which implements *AssetKey trait also implements the Debug trait. The asset cache then uses calls format!("{self:?}") to create the key. The key itself is going to be a dynamically allocated String of the length of the Debug formatting output. Finally, the String key is wrapped into an Arc, yielding yet another dynamic allocation, presumably to make it more convenient to use in async contexts.

• One issue is that there is no way to get something from the cache without going through the Debug-formatter, even if we already have the key when we did the initial insertion.
• Another issue is the requirement that the type implements Debug. Depending on the fields in the type this might be a significant amount of work, which requires the type to "optimize" the Debug implementation, for example not Debug formatting every vertex in a mesh. It is also simply the wrong tool for the job.
• This is also clearly inefficient in both execution time and memory usage. Strings are individually allocated and are variable length and the fact they are stored in an Arc causes a pointer indirection, hurting CPU cache performance. The effect on frame rate might currently be low, but on larger games with more assets, this system will scale towards the worst case.

An alternative

An alternative way to do keying is to use content hashing instead. We can keep all the *AssetKey types mostly intact, but make them implement a hashing trait that produces an u128 for example. This u128 should be returned to the user so any future accesses to the cache don't have to re-hash the key. We could also make it strongly typed by new-typing u128 into something like:

#[derive(Clone, Copy)]
struct CacheKey<T> {
    hash: u128,
    _phantom: std::marker::PhantomData<T>,
}

let hash: CacheKey<PixelTextureKey> = // created by hashing `PixelTextureKey`

This fixes all three issues listed above.

Note that we are not hashing the value that the key points to, we are hashing the key itself. For example:

#[derive(Debug, Clone)]
pub struct TextureFromUrl {
    pub url: AbsAssetUrl,
    pub format: wgpu::TextureFormat,
}

In this scenario, the TextureFromUrl itself is hashed, and this hash is then used to interact with the asset cache.

Singleton resources

This presents an interesting issue for "singleton assets" like the GPU itself. The current solution is to Debug-format a unit struct like pub struct GpuKey;, which returns the string "GpuKey". We could workaround it by doing the same thing by hashing the string GpuKey and everything continues to work. It does however feel a bit silly when these singleton resources should be directly accessible (without hashmap lookup), but that's a separate issue.

[ghost]

Originally yes when I thought we could replace the keys with ULID, this was incorrect. However, after the improved understanding, I still feel like the keying system can be made more efficient through content-hashing. Is my explanation of asset cache incorrect or incomplete?

[FredrikNoren]

(Sorry removed my comment because I thought this was an old issue :) @VinhTruongAmbient answer was to that comment)

[ten3roberts]

How would the hashing trait work for f32?

the std::hash::Hash, and in extension hashmaps don't work for structs using f32s (or f32s) directly for that matter.

Additionally: how would we guarantee sufficient entropy for the hashed u128? Since it is not pure random there is a high chance that collisions occur

[FredrikNoren]

@VinhTruongAmbient Hm so honestly this just seems "different" rather than strictly "better" to me. But the bigger problem here is that I don't see what real-world problem we're addressing here? You mentioned performance (cpu and memory), but I don't see any data to back that up? "Optimizing performance" without measuring is not something we should indulge in. There's a million different ways to do things, so I'm hesitant to change things unless it's very clear it's actually making something better.

[ghost]

How would the hashing trait work for f32?

the std::hash::Hash, and in extension hashmaps don't work for structs using f32s (or f32s) directly for that matter.

Additionally: how would we guarantee sufficient entropy for the hashed u128? Since it is not pure random there is a high chance that collisions occur

We might need to create our own hash trait which can hash f32 by reinterpreting it as a u32. This should be a sound operation because floats are standardized in Rust.

128 bits is a lot of entropy so collisions should be exceedingly rare, but if we wanted to be really paranoid a 256-bit would definitely be enough. In my previous company, we had databases with billions of elements with SHA256 as the key.

[FredrikNoren]

We're also doing things like loading a model, which points to a material, which points to a texture, all of which is loaded through the asset cache right now and de-duplicated (you can load the same model and/or material and/or texture from multiple locations in code and it still resolves to the same load), which I don't think content-addressed could solve at all (it would need a separate system, which would bring us back to square one).

[ghost]

@VinhTruongAmbient Hm so honestly this just seems "different" rather than strictly "better" to me. But the bigger problem here is that I don't see what real-world problem we're addressing here? You mentioned performance (cpu and memory), but I don't see any data to back that up? "Optimizing performance" without measuring is not something we should indulge in. There's a million different ways to do things, so I'm hesitant to change things unless it's very clear it's actually making something better.

I do think this improves how the developer interacts with the asset cache, for example not needing to go through Debug trait which is in my opinion a pretty unorthodox way to implement keying. Also because the hash key is Copy, there is no need to wrap it into Arc or clone it every time it crosses a thread boundary, which is nicer to the CPU but also simplifies the developer experience. For example, a struct that holds this key doesn't also need to be Arc and can implement Clone, Copy instead of only Clone.

As for performance, I think we have different viewpoints on what it means to "optimize performance". I wouldn't count this as actual optimization but rather it's about not doing work that doesn't give anything beneficial to us unless I am missing something from my understanding. As for providing data, I can set up a benchmark that really stresses the asset cache, but this feels like a pointless exercise because the cost of string formatting and allocations are real given that we understand how the processor and memory work. I grant that the title says "more efficient" which maybe is focused too much on the performance, but the points in the larger posts still hold.

[ghost]

We're also doing things like loading a model, which points to a material, which points to a texture, all of which is loaded through the asset cache right now and de-duplicated (you can load the same model and/or material and/or texture from multiple locations in code and it still resolves to the same load), which I don't think content-addressed could solve at all (it would need a separate system, which would bring us back to square one).

I think this should scenario behave the same right? Because the AssetKey is hashed, not the actual data that gets loaded with the key.

[ten3roberts]

How would the hashing trait work for f32?
the std::hash::Hash, and in extension hashmaps don't work for structs using f32s (or f32s) directly for that matter.
Additionally: how would we guarantee sufficient entropy for the hashed u128? Since it is not pure random there is a high chance that collisions occur

We might need to create our own hash trait which can hash f32 by reinterpreting it as a u32. This should be a sound operation because floats are standardized in Rust.

128 bits is a lot of entropy so collisions should be exceedingly rare, but if we wanted to be really paranoid a 256-bit would definitely be enough. In my previous company, we had databases with billions of elements with SHA256 as the key.

My question was rather the entropy of the hash functions, as (especially if we write our own) has functions tend to sacrifice some entropy/ for speed. Using or reusing the existing hasher would be very problematic since the hashing algorithm and stabilty and usage of quality over speed is subject to change.

Using random with u128 is fine, but not string hashing or similar

[ghost]

How would the hashing trait work for f32?
the std::hash::Hash, and in extension hashmaps don't work for structs using f32s (or f32s) directly for that matter.
Additionally: how would we guarantee sufficient entropy for the hashed u128? Since it is not pure random there is a high chance that collisions occur

We might need to create our own hash trait which can hash f32 by reinterpreting it as a u32. This should be a sound operation because floats are standardized in Rust.
128 bits is a lot of entropy so collisions should be exceedingly rare, but if we wanted to be really paranoid a 256-bit would definitely be enough. In my previous company, we had databases with billions of elements with SHA256 as the key.

My question was rather the entropy of the hash functions, as (especially if we write our own) has functions tend to sacrifice some entropy/ for speed. Using or reusing the existing hasher would be very problematic since the hashing algorithm and stabilty and usage of quality over speed is subject to change.

Using random with u128 is fine, but not string hashing or similar

Ah, I wasn't suggesting we write our own hash function, but just the trait that uses some other hash implementation to do it. There should be a plenty of options out there we can experiment with. SHA-256 works for sure since that's what I have used before for gigantic datasets, but the performance is not great compared to non-cryptographic hashes.

[ten3roberts]

Should we perhaps convert this to a discussion?

[FredrikNoren]

We're also doing things like loading a model, which points to a material, which points to a texture, all of which is loaded through the asset cache right now and de-duplicated (you can load the same model and/or material and/or texture from multiple locations in code and it still resolves to the same load), which I don't think content-addressed could solve at all (it would need a separate system, which would bring us back to square one).

I think this should scenario behave the same right? Because the AssetKey is hashed, not the actual data that gets loaded with the key.

Ah ok, I see, I misunderstood the proposal then; so basically this is just to move from debug to hashing for asset keys and to cache the result of that hashing?

[ghost]

We're also doing things like loading a model, which points to a material, which points to a texture, all of which is loaded through the asset cache right now and de-duplicated (you can load the same model and/or material and/or texture from multiple locations in code and it still resolves to the same load), which I don't think content-addressed could solve at all (it would need a separate system, which would bring us back to square one).

I think this should scenario behave the same right? Because the AssetKey is hashed, not the actual data that gets loaded with the key.

Ah ok, I see, I misunderstood the proposal then; so basically this is just to move from debug to hashing for asset keys and to cache the result of that hashing?

Yeah, that's right. Sorry for being misleading, I updated my original post for clarification.

[FredrikNoren]

We're also doing things like loading a model, which points to a material, which points to a texture, all of which is loaded through the asset cache right now and de-duplicated (you can load the same model and/or material and/or texture from multiple locations in code and it still resolves to the same load), which I don't think content-addressed could solve at all (it would need a separate system, which would bring us back to square one).

I think this should scenario behave the same right? Because the AssetKey is hashed, not the actual data that gets loaded with the key.

Ah ok, I see, I misunderstood the proposal then; so basically this is just to move from debug to hashing for asset keys and to cache the result of that hashing?

Yeah, that's right. Sorry for being misleading, I updated my original post for clarification.

Hm but if that's the case isn't this just about performance optimization then? The dev ux right now is just that you need to implement Debug, with the proposed it would be to implement Hash (and probably PartialEq?) so doesn't seem that different?

[ghost]

We're also doing things like loading a model, which points to a material, which points to a texture, all of which is loaded through the asset cache right now and de-duplicated (you can load the same model and/or material and/or texture from multiple locations in code and it still resolves to the same load), which I don't think content-addressed could solve at all (it would need a separate system, which would bring us back to square one).

I think this should scenario behave the same right? Because the AssetKey is hashed, not the actual data that gets loaded with the key.

Ah ok, I see, I misunderstood the proposal then; so basically this is just to move from debug to hashing for asset keys and to cache the result of that hashing?

Yeah, that's right. Sorry for being misleading, I updated my original post for clarification.

Hm but if that's the case isn't this just about performance optimization then? The dev ux right now is just that you need to implement Debug, with the proposed it would be to implement Hash (and probably PartialEq?) so doesn't seem that different?

Yeah, I didn't intend this to be a hugely different API that forces significant rewrites. I think the change can be implemented pretty easily because it's pretty much the same idea as Debug-formatting your struct and using the formatted String as the key. I do think the fact that the proposed u128 hash type is Copy makes it a lot easier to work with in async contexts.

Also, I proposed that you should be able to keep this u128 hash key when you insert the asset for the first time. Any subsequent accesses to the asset cache can then re-use the same key and skip the hashing routine. Yes, it improves performance, but why do the same work again when you don't need to 🙂.

[FredrikNoren]

Yeah, I didn't intend this to be a hugely different API that forces significant rewrites. I think the change can be implemented pretty easily because it's pretty much the same idea as Debug-formatting your struct and using the formatted String as the key. I do think the fact that the proposed u128 hash type is Copy makes it a lot easier to work with in async contexts.

Also, I proposed that you should be able to keep this u128 hash key when you insert the asset for the first time. Any subsequent accesses to the asset cache can then re-use the same key and skip the hashing routine. Yes, it improves performance, but why do the same work again when you don't need to 🙂.

Alright, so in that case there are two things to consider here:

First; I'm not 100% sure but I think you might get collisions if you just use the hash. I suspect that you would anyway need to be able to fall back to a full PartialEq, but then you'll have to bring the key with you (so you won't get Copy anyway).

Second; On the performance part, I want to make sure we don't get into the habit of assuming things when it comes to performance. That this is called a "More efficient AssetCache keying system" or that it talks about "Clearly inefficient" is premature; we really don't know that at this point. This suggestion is in my mind a hypothesis or an idea that might improve performance, and we should talk about it in those terms; i.e. "Here's something I think we should test to see if we can improve performance". Until we've measured I don't think we should ever say that something is actually better.

[ghost]

Alright, so in that case there are two things to consider here:
First; I'm not 100% sure but I think you might get collisions if you just use the hash. I suspect that you would anyway need to be able to fall back to a full PartialEq, but then you'll have to bring the key with you (so you won't get Copy anyway).

Yes, you might get collisions with hashing operation due to the pigeonhole principle. But what are the chances of that happening? A hash length of 256 bits already makes it so that the universe will end sooner than we will find a collision.

If we are talking about the theoretical chance of collisions, remember that there is nothing in Debug that guarantees that there won't be cases where two different Debug implementors won't produce the same string. One easy example is floating point NaN's. There are many possible NaN's, but all of them get formatted into NaN, while hashing (or anything else that worked on bits directly) would have produced the correct result.

Then there is the case of having to "optimize" Debug printing just to make this keying system work. Here is one example that I have already removed from the code base:

Here meshes with the same number of vertices, but at different positions would produce the same key. The name is the only thing that could have saved this case, but there is no guarantee that name is unique across all meshes.

If we still wanted to be perfectly no-collision, then at the very least the Debug should be switched to something like bincode and serialize the type into a Vec<u8> and store that as the key instead.

Second; On the performance part, I want to make sure we don't get into the habit of assuming things when it comes to performance. That this is called a "More efficient AssetCache keying system" or that it talks about "Clearly inefficient" is premature; we really don't know that at this point. This suggestion is in my mind a hypothesis or an idea that might improve performance, and we should talk about it in those terms; i.e. "Here's something I think we should test to see if we can improve performance". Until we've measured I don't think we should ever say that something is actually better.

I agree with this principle, especially on anything that is more complicated or non-obvious. In this specific case, however, I disagree that we don't know whether or not a fixed 128/256-bit value is more efficient than a string of 455 characters long:

BackgroundKey(AnimationClipRetargetedFromModel { clip: TypedAssetUrl(http://192.168.1.130:8999/content/assets/Robot%20Hip%20Hop%20Dance.fbx/animations/mixamo.com.anim, PhantomData<ambient_std::uncategorized::asset_url::AnimationAssetType>), translation_retargeting: None, retarget_model: Some(TypedAssetUrl(http://192.168.1.130:8999/content/assets/Peasant%20Man.fbx/models/main.json, PhantomData<ambient_std::uncategorized::asset_url::ModelAssetType>)) })

Or whether allocating something is more efficient than not allocating something. I feel like this is clear enough that it doesn't need further elaboration. Even if allocations only took 1 cycle (they do not), 1 is still greater than 0.

I'll grant that you are probably right that even with these inefficiencies you are not able to see them in the profiler, because other systems are likely to dominate (although we don't have large enough realistic benchmarks to demonstrate this either way). And I'll also grant that it might be premature to change this now because we have better things to do. But ultimately the inefficiencies are still real and won't go away because we decided that it is not a big deal right now.

[ghost]

Side-topic: we are currently assuming that a specific key always maps to a specific value, but this assumption might be false if, for example, the file under the URL has changed. I don't know if the plan is to implement change detection (for hot reloading) into AssetCache specifically or if will it be a completely separate system, but regardless a true content-hashing will be required at some point.