Ayaz Hafiz (Oct 03 2022 at 22:46): Ayaz Hafiz (Oct 03 2022 at 22:46):There have been discussions about adding the Hash ability and a hash-based Dict/Set implementation for some time, but AFAIK, there isn't a concrete description of the API to be exposed (please correct me if I'm wrong here). So to kick this off, here is a barebones API that I think could work for us, at least to get started:
Hash has
hash : a, hasher -> hasher | a has Hash, hasher has Hasher
Hasher has
addBytes : a, List U8 -> a | a has Hasher
complete : a -> U64 | a has Hasher
hashValue : a, hasher -> U64 | a has Hash, hasher has Hasher
hashValue = \val, hasher ->
hash val hasher |> complete
we'll derive the Hash ability for structural types, and Hasher won't be derivable - it will be an ability an author of hashing algorithms implements to support hashing types that implement Hash.
I'm intentionally offering a simple API here so we can iterate as needed. Thoughts?
Richard Feldman (Oct 03 2022 at 23:01):could Hasher run faster if it had all the methods of Rust's Hasher?
Richard Feldman (Oct 03 2022 at 23:01):so for example it didn't need to heap-allocate a List when given an integer
Ayaz Hafiz (Oct 03 2022 at 23:03):I was thinking the derivers would always call Num.toBytes for when it was time to hash a number. once we have constant lists that would be zero-costs since you could just treat the number as a slice into the list of bytes
Ayaz Hafiz (Oct 03 2022 at 23:04):But I think having a write* for each number type also makes sense. That's what we do with Encoding/Decoding as well
Richard Feldman (Oct 03 2022 at 23:04):hm, but wouldn't that only be true of a statically-known number?
Ayaz Hafiz (Oct 03 2022 at 23:04):No, because a U64 is equivalent to a slice of 8 bytes right
Brendan Hansknecht (Oct 03 2022 at 23:05):I think we will want follow rust. The cost of going to bytes and not getting optimizations for the specific algorithm will be high.
Ayaz Hafiz (Oct 03 2022 at 23:06):Rust's default implementations of Hash also take a slice into the bytes of a number: https://doc.rust-lang.org/src/core/hash/mod.rs.html#373-375
Brendan Hansknecht (Oct 03 2022 at 23:06):The core algorithm would to a lot of extra checks that could be removed with compile time know sizes and separately optimized implemtenation.
Richard Feldman (Oct 03 2022 at 23:07):ok, so separate question: it seems that Rust hardcodes the output to be U64 - is that good? :sweat_smile:
Richard Feldman (Oct 03 2022 at 23:07):like as opposed to requiring the hasher to also provide (for example) a U32 and U128 output
Richard Feldman (Oct 03 2022 at 23:08):for example, I know some hashing algorithms are much faster at making 32-bit than 64-bit numbers
Richard Feldman (Oct 03 2022 at 23:08):so maybe it would be useful to have that as an output option, for when you know you're using one of those
Richard Feldman (Oct 03 2022 at 23:08):and similarly, maybe in the future there would be a desire for 128-bit hashes? I don't really know enough to say whether that would be true or not though
Ayaz Hafiz (Oct 03 2022 at 23:09):One challenge there is that not all hashing algorithms can support smaller-sized output sizes
Brendan Hansknecht (Oct 03 2022 at 23:10):The question is what is the goal? If we want Hasher for hash maps, it should be Nat or U64 or something of that sort. If we also want it to support cryptographic hashes, it would need to support other sizes.
Richard Feldman (Oct 03 2022 at 23:10):I definitely think hash maps is the main goal
Brendan Hansknecht (Oct 03 2022 at 23:12):Then I would say the output should be either Nat or U64.
Richard Feldman (Oct 03 2022 at 23:13):trying to output Nat sounds tricky with all the arithmetic involved, so I guess U64 it is :sweat_smile:
Brendan Hansknecht (Oct 03 2022 at 23:14):Also, I was looking at a rust implementation of wyhash, I am am surprised that everything is done with bytes. I would assume the overhead would be quite expensive, but I guess they inline everything which essentially removes the cast to bytes and just converts things to u64.
Ayaz Hafiz (Oct 03 2022 at 23:16):this is kind of interesting re. u64 vs usize hashing in Rust: https://github.com/rust-lang/rust/pull/36595#issuecomment-249725336
Ayaz Hafiz (Oct 03 2022 at 23:20):I am am surprised that everything is done with bytes. I would assume the overhead would be quite expensive
It looks like they need 32 bits at a time exactly: https://github.com/eldruin/wyhash-rs/blob/8707fbe33bcd8354819712a93a4457cc83c367c2/src/v1/functions.rs#L78-L79 I bet most of the bytes you get are just direct indexes into values on the stack so it's not a big deal
Brendan Hansknecht (Oct 03 2022 at 23:21):Just for a quick reference, with current roc, hashing a u64 is about 3x faster than converting a u64 to a list and then hashing it.
Brendan Hansknecht (Oct 03 2022 at 23:23):This is with reusing the same list and using List.set to avoid calling roc_alloc
Brendan Hansknecht (Oct 03 2022 at 23:25):Definitely some future work will make this better, but I am not sure how much better.
Brendan Hansknecht (Oct 03 2022 at 23:30):I was thinking the derivers would always call Num.toBytes for when it was time to hash a number. once we have constant lists that would be zero-costs since you could just treat the number as a slice into the list of bytes
I don't think we could make this a seamless slice. It would have to be something else special. There would be no actual memory to point to due to the number being in a register. You can't just put the number on the stack because once you return from a function, it could get clobbered.
Brendan Hansknecht (Oct 03 2022 at 23:30):Thus, you would still have to call roc_alloc and put it on the heap to keep the memory around.
Brendan Hansknecht (Oct 03 2022 at 23:31):Otherwise, the list returned from Num.toBytes would need to ensure it never escaped the current scope without allocating first.
Brendan Hansknecht (Oct 03 2022 at 23:32):So I guess not having real references means that we will have issues that Rust does not run into.
Brendan Hansknecht (Oct 03 2022 at 23:34):With all this said, I like the idea of requiring a hash function for all unsigned numbers. All other numbers will just automatically get mapped to those number types. Everything else would get mapped to a List of bytes (or a List of some unsigned number type).
Brendan Hansknecht (Oct 03 2022 at 23:36):Also, seamless slices may make this point mute, but I think it might also be useful to have a function with the signiture List U8 -> {transmuted: List U64, remainder: List U8} that essentially is a memory transmute with limited scope related to number types.
Ayaz Hafiz (Oct 03 2022 at 23:42):I don't think we could make this a seamless slice. It would have to be something else special. There would be no actual memory to point to due to the number being in a register. You can't just put the number on the stack because once you return from a function, it could get clobbered.
I don't understand why this is a problem - if I have a U64 rvalue, I can transmute that to a [u8; 8] rvalue, and then I can create a RocList from that with length 4 and zero capacity. The U64 doesn't need to be bound anywhere. What am I missing here?
Brendan Hansknecht (Oct 03 2022 at 23:47):When we return a list, we don't do anything to it's data. We just return a pointer, length, and capacity. There also is no small list.
if we created the list from a reference to a U64. The U64 would be bytes on the stack. The list would point to those bytes. If we return, those bytes now should be considered clobbered with the stack frame. The next function call might overwrite it.
If we instead put the bytes of the U64 onto the heap, it will cost a call to roc_alloc.
Ayaz Hafiz (Oct 03 2022 at 23:49):oh, I see. there is no small list optimization
Ayaz Hafiz (Oct 03 2022 at 23:49):okay got it
Ayaz Hafiz (Oct 03 2022 at 23:49):I was assuming the list owned the elements
Brendan Hansknecht (Oct 03 2022 at 23:51):I guess we could technically add small list optimization for types 16 bytes or under (due to padding constraints). That would also make this fast.
Ayaz Hafiz (Oct 03 2022 at 23:53):Yeah, that seems ideal. Then Num.toBytes also wins in general, not just for hashing purposes
Ayaz Hafiz (Oct 03 2022 at 23:54):elsewhere this might be annoying though, I would guess most data structures are >= 16 bytes so you could only put one of them in the small list before having to roc_alloc
Brendan Hansknecht (Oct 03 2022 at 23:58):For a record, you wouldn't turn the entire thing into bytes. You would instead call hash an each element within the record. So the small list optimization should still help.
Brendan Hansknecht (Oct 03 2022 at 23:59):This is because opaque types may not want every field hashed, lists need to hash the data they point to, and you have to be careful around hashing padding.
Brendan Hansknecht (Oct 04 2022 at 00:08):Anyway, I think as a summary, the api you mentioned should be fine if we add some form of small list optimization. If we do not add some form of small list optimization, I think that we should add a function for every unsigned integer type as well. (aside, not sure how the api works with bool and tags in general)
Richard Feldman (Oct 04 2022 at 00:29):yeah I think it's best to assume no small list optimization here
Ayaz Hafiz (Oct 04 2022 at 00:47):i think for every integer type is fine, to align with Encode/Decode. Bools/tags should not need any ability member, though we will probably also want a way to grab a tag union’s discriminant from user space to make hashing them easier
Brendan Hansknecht (Oct 04 2022 at 00:49):Ah, makes sense.
Brendan Hansknecht (Oct 04 2022 at 00:49):Then let's go with that. Hash really is just a weird form of encode that loses information.
Richard Feldman (Oct 04 2022 at 01:10):it also can't fail, unlike Encode
Brendan Hansknecht (Oct 04 2022 at 01:16):Encode can fail....interesting. i would have guessed only decode can fail.
Brendan Hansknecht (Oct 04 2022 at 01:31):Oh, one more potential change, but it would require some for of transmute type function (List Num a -> List U8, though it could also theoretically support some record types if they can safely be converted to bytes). Looking at the rust Hash trait, it also has hash slice. This is specifically so that some types can make their hash function just hash the list as a list of bytes instead of a list of individual elements. This would greatly improve the speed of hashing for a list of ints for example.
Richard Feldman (Oct 04 2022 at 01:32):also worth noting that for Dict to be generalized, we'll need not only Hash but also Eq - although for now everything kinda "has Eq" anyway, so that's not a blocker for anything except custom equality
Richard Feldman (Oct 04 2022 at 01:32):Encode can fail because some serialization formats can't represent every type Roc supports - this didn't occur to me at first, but then I realized serde's serialize can fail and started thinking about why they would do that...
Richard Feldman (Oct 04 2022 at 01:36):another Zulip thread talked about some values that aren't representable in JSON: integers too big to fit in a F64 (since that's what JS uses for its number types) and NaN
(I don't think the JSON spec actually puts a cap on max integer size, actually, although in practice there's a limit to what a JS engine will decode successfully)
Ayaz Hafiz (Oct 04 2022 at 02:53):yeah we’ll need some more stuff for abilities to support binding variables to both Hash and Eq. I made an issue about that earlier today, will try to implement tomorrow
Ayaz Hafiz (Oct 04 2022 at 02:56):Also re tag discriminants- I think we can get away with not exposing that in user space. Derived Hash impls can use a discriminant-extracting function we hide away, and Hash for opaque types should decide how to represent discriminants themselves. That way we avoid leaking the discriminant representation through a surface function (you could still maybe figure it out by hashing a tag union, but only if the union has no tags that have payloads)
Brendan Hansknecht (Oct 04 2022 at 06:15):Also, just did some testing of my wyhash implementation again. If you tell roc to always inline all of the wyhash function, the performance is pretty decent. Compared to the original C++ implementation.
Single byte -> ~ 0.5x
256B chunks -> ~0.66x
65KB chunks -> ~1x
As an aside, if we write direct functions like I created for U64, it can actually be faster than the C++ version. Though not by much iirc.
Brian Carroll (Oct 04 2022 at 07:24):Is that a time metric or a throughput metric?
Brian Carroll (Oct 04 2022 at 07:25):Ah based on your last comment it must be throughput
Qqwy / Marten (Oct 04 2022 at 10:35):Richard Feldman said:
also worth noting that for
Dictto be generalized, we'll need not onlyHashbut alsoEq- although for now everything kinda "has Eq" anyway, so that's not a blocker for anything except custom equality
Eq is necessary to handle hash conflicts I presume?
If so, IIRC there are ways around this, by having a second (and third if necessary, etc.) round of hashing if a conflict arises. Let me see if I can find the literature about this again.
EDIT: No, I was mistaken. This is not possible.
Qqwy / Marten (Oct 04 2022 at 10:37):About working with bytes vs U32 vs U64: Many 'fast' (that is, non-cryptographic) hashing algorithms try to harness SIMD as much as possible. My educated guess is that this might be why some hashing algorithms ostensibly work on bytes but still are able to be fast.
Qqwy / Marten (Oct 04 2022 at 10:57):Richard Feldman said:
another Zulip thread talked about some values that aren't representable in JSON: integers too big to fit in a
F64(since that's what JS uses for its number types) and NaN(I don't think the JSON spec actually puts a cap on max integer size, actually, although in practice there's a limit to what a JS engine will decode successfully)
:upside_down: I read all seven variants of the JSON spec a while back while working on the Roc JSON parser.
I recommend https://seriot.ch/projects/parsing_json.html for anyone who wants a brief summary of the intricacies of working with JSON.
Any parser that turns all numeric values encountered in JSON to IEEE754 double-precision floats (such as, but by far not limited to, JavaScript's built-in JSON parser) is unable to parse integers outside of the range (-2^53..2^53) because a 64-bit float has a 52-bit mantissa.
Most notably Twitter encountered this problem in the wild when moving their API ids from sequential integers to 'snowflakes' (IDs with rough ordering because the first part of their number is based on a timestamp) https://developer.twitter.com/ja/docs/basics/twitter-ids.
The standard itself confusingly claims both "A JSON parser MUST accept all texts that conform to the JSON grammar" and in the same paragraph, "An implementation may set limits on the range and precision of numbers.". (section 9 of RFC8259). That's as much clarity as we get.
So: While the spec does not explicitly disallow it, how large numbers are handled is implementation defined, and thus encoding large numbers in JSON is not portable.
Another relatively well-known tidbit is that NaN and +-Infinity are not allowed in JSON.
Another edge case is raw (non-Unicode) bytestrings. These are also plainly not allowed.
A less well-known problem is that older standards only allowed arrays and objects at the top level in JSON. This restriction was relaxed in newer versions of the standard (RFC7158 from 2014), but many parsers in the wild still follow this older rule. I've spent two full days of debugging on a professional project once because of this problem.
OK, sorry for my slightly off-topic rant :sweat_smile:
The tl;dr: Hash encoding is definitely different enough from other kinds of encoding to merit its own ability.
Brendan Hansknecht (Oct 04 2022 at 15:04):Is that a time metric or a throughput metric?
Yeah, it was a throughput metric.
That being said, I just worked on it this morning to see if I could close the gap. The answer is yes. We can get 100% performance parity with the C++ version for those benchmarks.
For the single byte benchmark, I had to improve my test runner and run longer (the hash was actually running fast).
For the other two benchmarks, I changed all of my additions and subtractions to wrapping addition and subtraction (which should be 100% safe assuming no bugs).
Now all of those benchmarks are approximately the same speed as C++ :tada: (Though we more heavily rely on inlining in small List cases)
Richard Feldman (Oct 04 2022 at 15:45):wow, beautiful! I guess that's the first pure-Roc hashing function to achieve performance parity with C++! :tada:
Richard Feldman (Oct 04 2022 at 15:46):did that require telling the Roc compiler to do more inlining than it normally would? Or was this with a stock (e.g. nightly) compiler build?
Brendan Hansknecht (Oct 04 2022 at 16:01):This is with the modified compiler that does more inlining. Without it the performance story is much worse different. ~2x slower for small lists and ~10x slower for large lists.
Brendan Hansknecht (Oct 04 2022 at 16:04):I wonder if we should increase llvms default inline aggressiveness (or add a flag to modify it. The reverse of -opt-size). Due to our extra checks on math operations and lists sizes, functions are less likely to get inlined than the c equivalent without the checks.
Brendan Hansknecht (Oct 04 2022 at 16:09):In our case, we use the same value rust uses, iirc, which is 275. For hashing, the magic number seems to be about 550.
Brendan Hansknecht (Oct 04 2022 at 16:10):Otherwise, a more direct solution is to special case the hash module, but the feels less great.
Brendan Hansknecht (Oct 04 2022 at 16:12):In this specific case, there is no notable executable size difference.
Richard Feldman (Oct 04 2022 at 16:13):I'm definitely game for trying out increasing that number! Seems like an easy knob to turn, and if we see problems from it in other programs we can always reevaluate
Brendan Hansknecht (Oct 04 2022 at 16:18):I guess in the future if someone starts looking into binary size bloat (and -opt-size is too slow), we will have a good hunch of what to look into.
Brendan Hansknecht (Oct 05 2022 at 04:57):So I was doing some tests of tracking state in the hasher vs passing in a list of bytes. So in one form, it basically adds bytes one at a time, but keeps track of an internal state to batch operations. In the other version, it processes a list of bytes as a whole.
As expected, the processing the list of bytes as whole is way faster (~5-10x). This is even the case if I force a copy in the list of bytes case. There may be something wrong with my code gen, but I think it is correct. Also, to accumulate state, I originally used a statically sized list that never got reallocated. That was slow, so I tried the equivalent of an array....I don't advise it. It was faster than the list version, but still way slower than the version without state.
The Must Fun Data Structure to Use
Ayaz Hafiz (Oct 05 2022 at 05:06):That's really interesting. Do you have two diffs? I'd love to see what mono and LLVM we produce
Ayaz Hafiz (Oct 05 2022 at 05:06):but yeah it sounds like we should flip the impl to generate a list of bytes whenever possible
Brendan Hansknecht (Oct 05 2022 at 05:30):Here is a monster diff using the record to store data. It only works if you set the number of elements to hash to x where x > 48 and x%48=16. That was just the easiest case to get working: https://github.com/bhansconnect/roc-dict/commit/8dbb8e5abe72e993c276e5140c34499a1d4ca9f1
Brendan Hansknecht (Oct 05 2022 at 05:31):Also, the performance difference is much worse if you increase the compilers inline threshold (I set it to 750).
Brendan Hansknecht (Oct 05 2022 at 14:56):I also added a stateful list based version for reference. Requires a modified compiler for any vague performance. Will upload and post branch here shortly: https://github.com/bhansconnect/roc-dict/commit/67f0ef0b458a96107cca3309605022f919e48782
Brendan Hansknecht (Oct 05 2022 at 15:42):The hashing-perf branch has my performance changes for running hashing.
Brendan Hansknecht (Oct 05 2022 at 15:42):Also, I realized that in the last commit I pushed, I accidentally did so with debug = true in the platform. If doing benchmarks, make sure to change that back to false.
Brendan Hansknecht (Oct 05 2022 at 16:28):Also, I just pushed an update stateful List based version that uses a ring buffer to avoid extra copying. It is now close to the record based version in performance. Still much slower than the stateless List of bytes based version even if we are forced to copy the list of bytes on every call to hash.
Brendan Hansknecht (Oct 11 2022 at 19:57):For hashing, do you think it is worth supporting unordered hashing? Then you could make a set hashable for example (without insertion order mattering).
Brendan Hansknecht (Oct 11 2022 at 19:59):I think to support it, either it would have to be added directly to the hasher API, or it would need to expose some way to create a new/sub-hasher from the Hasher API. That way, you can hash individual elements and merge them in an unordered manner. So essentially you need some special accumulation.
Brendan Hansknecht (Oct 11 2022 at 20:01):We could expose something like Hash.hashUnordered that would be generic between all hashers.
Ayaz Hafiz (Oct 11 2022 at 20:01):Could that be implemented as the custom hash implementation for a container, rather than something exposed by the ability?
Brendan Hansknecht (Oct 11 2022 at 20:04):Not with the current hasher impl. Cause you need to hash essentially
Brendan Hansknecht (Oct 11 2022 at 20:05):So you can't only accumulate with add*
Ayaz Hafiz (Oct 11 2022 at 20:08):Can you elaborate by what you mean by "unordered friendly manner" here? Ultimately the elements are going to follow some ordering, how do you want to hash them?
Brendan Hansknecht (Oct 11 2022 at 20:10):One of the simplest ways and what absl does (performant, though i don't think it is guaranteed to be as good of a hash). Sum the hash of each element with wrapping addition. Also add 1 every time you overflow to not lose entropy. Then take that final value do a proper hash mix/combine with the initial state.
Brendan Hansknecht (Oct 11 2022 at 20:11):A more mathematically correct way would sort the hashes and then hash the hash list. But that costs a lot of memory space. Either way require hashing each item with a clean state.
Ayaz Hafiz (Oct 11 2022 at 20:14):I see
Ayaz Hafiz (Oct 11 2022 at 20:14):if you provide the container a constructor to build a hasher this is not a problem though, right? That's what Rust does with default type variables I think
Brendan Hansknecht (Oct 11 2022 at 20:19):Ah, so you pass a constructor into the containers hash function along with your current hasher.
Brendan Hansknecht (Oct 11 2022 at 20:20):But wouldn't that not match the hash ability API anymore?
Ayaz Hafiz (Oct 11 2022 at 20:20):Or, the container keeps the hash function in their data. Then it can use that in its hash implementation
Brendan Hansknecht (Oct 11 2022 at 20:21):Seems odd to add that to the constructor of every Set for example....so I don't particularly like that solution.
Ayaz Hafiz (Oct 11 2022 at 20:21):Well, you could have a default constructor that provides the default hasher, whatever that is
Ayaz Hafiz (Oct 11 2022 at 20:23):another downside of this though is that e.g. Set would gain an extra type variable. You could expose Set as the default alias with the default hasher though, and have an SetWithHasher (better name needed) as the actual implementation folks can use if they want to use a custom hasher.
Ayaz Hafiz (Oct 11 2022 at 20:24):e.g.
SetWithHasher k hasher := {makeHasher : {} -> hasher, ...} | hasher has Hasher
Set k : SetWithHasher k DefaultHasher
empty : Set k
emptyWithHasher : hasher -> Set k hasher
This is needed if you want a container that is generic over the hashing algorithm anyway
Ayaz Hafiz (Oct 11 2022 at 20:25):I guess the other option is to expose the "sub hasher" constructor on the Hasher ability, but I don't know how prudent that is - like what if you want to create a sub hasher with other configuration parameters? Or is that not an actual concern
Brendan Hansknecht (Oct 11 2022 at 20:25):It seems wrong to have a hash function that takes a hasher but then hash with a different algorithm. Maybe someone intentionally wants to use a stronger hash function. They would assume the set would use the hasher they provide to it's hash function, but it wouldn't.
Ayaz Hafiz (Oct 11 2022 at 20:26):Ah, you're talking about hashing Set itself
Brendan Hansknecht (Oct 11 2022 at 20:26):I think mostly you just want to create a version with a reset internal state.
Brendan Hansknecht (Oct 11 2022 at 20:26):I don't think you would change any config
Brendan Hansknecht (Oct 11 2022 at 20:27):Yeah, hashing set itself or anything else that is unordered.
Ayaz Hafiz (Oct 11 2022 at 20:27):hmm okay
Ayaz Hafiz (Oct 11 2022 at 20:28):so we would need
Hasher has
# .. the other stuff
new : a -> a | a has Hasher
yeah?
Ayaz Hafiz (Oct 11 2022 at 20:29):How common of use case is this? I had never really heard of this rehashing idea before, I've only ever seen the appending to a constant hasher and calling "finish" at the end
Brendan Hansknecht (Oct 11 2022 at 21:02):Literally only required for unordered hashing and not needed for anything else
Brendan Hansknecht (Oct 11 2022 at 21:02):Unordered hashing is pretty rare.
Brendan Hansknecht (Oct 11 2022 at 21:02):But yeah, thats all you would need
Ayaz Hafiz (Oct 11 2022 at 21:11):on the other hand you would need this if you want a hashmap/hashset that is unordered but you want to preserve equality under hashing, ie x = y => hash(x) = hash(y) right
Ayaz Hafiz (Oct 11 2022 at 21:12):which is a goal we want
Ayaz Hafiz (Oct 11 2022 at 21:12):so I feel like we should add this
Brendan Hansknecht (Oct 11 2022 at 21:18)::+1:
Richard Feldman (Oct 11 2022 at 21:47):yeah the relationship with equality was my first thought here
Richard Feldman (Oct 11 2022 at 21:47):so given where we ended up on equality for sets and dictionaries, I agree we should do unordered hashing for them too!
Brendan Hansknecht (Oct 11 2022 at 23:18):One other random thought/questions:
Wyhash (in it's default form) depends on 128bit multiplication. On some devices, that will not be directly support and will be slower (32 bit devices, many arm devices that aren't M1, wasm?). This may be a case where we want some sort of lowlevel that can switch out the default standard library hashing implementation. For example, absl, uses cityhash for those devices. Also, wyhash has an alternate form that swaps out the 128bit multiplication.
Do we have a way/want to support this? As I see it, the main upside is performance and the main downside is that hashes may not be the same across different devices (based on cpu architecture).
Richard Feldman (Oct 11 2022 at 23:21):makes sense to me!
Ayaz Hafiz (Oct 11 2022 at 23:26):agreed- how would a lowlevel for that look like? what would we need to support? just something that takes a list of bytes and spits out a hash, or something more?
Brendan Hansknecht (Oct 11 2022 at 23:28):I was more thinking some sort of compile time constant to select between two different hashers both implemented in Roc.
Brendan Hansknecht (Oct 11 2022 at 23:29):Cause I think the hashing algorithms are fine to write in Roc.
Ayaz Hafiz (Oct 11 2022 at 23:39):yeah we can make that happen
Brendan Hansknecht (Oct 11 2022 at 23:47):Oh, just realized one other thing while porting. I have a function that crashes if it fails to get a value from a list. It should never fail (fail a bug in the implementation). How should I write that function in the standard? Should I somehow propagate up the result? Should I just default to 0? Should I just leave in the crash? Maybe make a better named function for the crash?
getByte : List U8, Nat -> U8
getByte = \list, index ->
when List.get list index is
Ok b -> b
_ -> 0 - 1
is there any way you can get rid of that branch?
Ayaz Hafiz (Oct 12 2022 at 00:28):i can give it a pass if you like if you have the source
Ayaz Hafiz (Oct 12 2022 at 00:28):would could expose a lowlevel unreachable to built ins but that isn’t ideal
Brendan Hansknecht (Oct 12 2022 at 00:32):I really don't think so, I ultimately have to get data from the list. I can't walk the list because I want to load data in chunks without the cost of managing state and accumulation. Also, at the end there is a chance that we actually have to shift backwards and reanalyze some bytes.
Brendan Hansknecht (Oct 12 2022 at 00:36):Also, it is for porting this: https://github.com/bhansconnect/roc-dict/blob/main/examples/Wyhash.roc#L121 to the standard library.
Brendan Hansknecht (Oct 12 2022 at 00:37):Basically a lot of looping in various chunk sizes (starting big and getting smaller) then loading a bunch of blocks of bytes as U64s. Then hashing those blocks.
Brendan Hansknecht (Oct 12 2022 at 00:40):The functions that actually grab from the list are they wyr3, wyr4, and wyr8 functions that load up to 8 bytes into a U64.
Richard Feldman (Oct 12 2022 at 00:49):hashes being different shouldn't matter, right? Since we don't expose hash ordering anyway, people shouldn't be able to tell other than performance
Richard Feldman (Oct 12 2022 at 00:51):also would getUnsafe work to get rid of the branch? We already have a lowlevel for that, and could just let Dict implement something that compiles down to it too
Brendan Hansknecht (Oct 12 2022 at 01:17):Hashes being different I guess wouldn't be exposed to the user at all (past performance). We aren't exposing the algorithm and there won't be a way to serialize a dictionary that includes the hashes.
getUnsafe should work... Thanks!
Last updated: Jun 16 2026 at 16:19 UTC