solana-program-library icon indicating copy to clipboard operation
solana-program-library copied to clipboard

[token-2022] Suggested alternative extension dedup (ZELLIC 4.5)

Open samkim-crypto opened this issue 2 years ago • 1 comments

The implementation of get_total_tlv_len(...) takes the slice of provided extension_types and deduplicates the collection before summing each of their tlv_lens. The implementation uses a for loop that calls Vec::contains(...). For small number of extensions this may be okay, but in calls to realloc, this could result in slow code if callers are inefficient with passed up extension (offering duplicates, for example).

A suggested alternative would be to use a HashSet here. For performance, FxHashSet may be used if solving for this situation is desired.

samkim-crypto avatar Nov 18 '22 06:11 samkim-crypto

I was personally curious about this issue, so I did some simple test to compute the compute units when deduping using a vector and using a hashset (it was difficult to test directly on token-2022).

It seems like deduping using Vector::contains should outperform the use of hashsets for vectors of length below 76. Hashsets could be cheaper beyond vectors of size > 76. Therefore, it is reasonable to stick with the current implementation since, with the total number of extensions that we have currently, it seems unlikely for get_total_tlv_len(...) to be called on a vector of 76 or more extensions.

samkim-crypto avatar Nov 21 '22 11:11 samkim-crypto