Why do payload types need to be bitwise comparable in static_map?

[kevkrist]

Why do values need to be bitwise-comparable in static_map (since keys are unique)? This is preventing the use of float as the value type, which would be valuable.

[sleeepyjack]

We use atomic compare-and-swap operations to swap keys/payloads into slots in a concurrency-safe manner. These CAS instructions work on bitwise comparison, hence the restriction. By default, we make the decision if a given type is bitwise comparable based on the result of std::has_unique_object_representations<T>. However, there might be cases where user-defined types are actually bitwise comparable, but the STL facility doesn't mark it as such. For these cases we provide a helper macro CUCO_DECLARE_BITWISE_COMPARABLE(T).

float, for instance, has no unique object representation. However, if you as the user can guarantee that in your usecase float is actually bitwise comparable, then declaring CUCO_DECLARE_BITWISE_COMPARABLE(float) will allow cuco to use float as key/payload type.

[kevkrist]

Thanks for the tip!

I think I understand, though a little more clarification would be very helpful (thanks for your patience!) -- is the CAS is done on the key-value pair, then, rather than just on the key? I can guarantee, for example, that a cuco::pair<uint32_t, float> key-value pair has a unique object representation, inasmuch as the keys are unique, but this is independent of the float type of the value. I guess I'm a little lost that cuco::is_bitwise_comparable_v(T) is asserted for the value type T, but not for the key type Key in static_map.

[sleeepyjack]

We internally dispatch different insertion strategies depending on the key/value types and GPU architecture to achieve best performance. If sizeof(Key)+sizeof(Payload) <= 8, we can swap the entire pair into a slot with a single "packed" CAS operation. If the combined size exceeds the GPUs native CAS size, we swap the key and the payload in separately. This is done by either a back-to-back CAS strategy or a CAS operation on the key followed by a dependent relaxed write operation on the payload.

To answer your question regarding cuco::is_bitwise_comparable_v(T): The most restrictive strategy (and the fastest one too) here is the packed CAS approach, which requires both keys and payloads to be bitwise comparable since they both participate in the CAS operation.

[sleeepyjack]

AFAIK the only cases where float can have equivalent but different bit representations are

• -0.0 vs. +0.0
• different representations for NaN
• unnormalized floating point values

If you make sure none of these occur in you application it should be fine to declare CUCO_DECLARE_BITWISE_COMPARABLE(float).

[kevkrist]

Got it. Thanks!

[jrhemstad]

It would complicate the implementation a bit, but we could consider skipping the packed-CAS code path when is_bitwise_comparable_v(Key) && !is_bitwise_comparable_v(Value).

Then it would still work, just not as fast.

[kevkrist]

I'm getting everything to work now, so it doesn't seem worth the complication at this point in time (also, faster is better!). (Edited) It might be nice to have an example with a floating-point type for future users (unless I'm missing one), though I understand that it's possible that the use of float might introduce incorrect CAS results.

Thanks all!

[sleeepyjack]

we could consider skipping the packed-CAS code path when is_bitwise_comparable_v(Key) && !is_bitwise_comparable_v(Value)

@jrhemstad I'd rather keep performance-related settings as an opt-out rather than opt-in, i.e., we could add a global flag CUCO_REQUIRE_BITWISE_COMPARABLE_PAYLOADS which is on by default but can be turned off by the user.

This, of course, should be documented with an example, as @kevkrist suggested.

Closing this discussion here but opening a new issue to track the idea.

[sleeepyjack]

Opened #427