2
$\begingroup$

Traditionally, hash functions are single-threaded, and have the 'Init-Update-Final' API style. This is true of MD5, SHA-1/2/3, BLAKE2, to name a few.

However, there have been proposal of parallel hash functions, and tree-hashing. BLAKE3 and KangarooTwelve are among these.

If we continue to use the IUF API, then data-availability may become a bottleneck to the overall performance. I could imagine that, these hashing functions are "active" in that, they're provided with a large, and sometimes complete message blob, so that the hashing API subroutines can decide for themselves how to consume the data, and how to spawn threads.

Another problem I can think of is, the system load with regard to creating concurrent threads for data processing. In an IUF hash implementation, resource usage can be limited to those of executing the hashing algorithm and keeping a hashing context state; but creating threads for parallel and tree hashing involves system resources to back a thread and relevant synchronization primitives. The latter may require caller/user configuration and tuning I believe.

Yet another problem I can think of is, the problem of later message segments arriving before earlier message segments. While the simple solution of process-and-buffer is obvious, too many yet-processable segments may become a burdon for the process in the memory dimension.

Now, before I embark on a journey to implement parallel and tree hashing algorithms in my hobbyist project, I should have an understanding of typical and/or ideal API design that can maximize the performance potential of these types of hashing algorithms.


Side Note: A touch on dispatch-like API adaptation will be a bonus. Specifically, if the answer discuss both the use of typical threading APIs (e.g. C11 and/or POSIX threads), AND dispatch-like APIs such as Apple's Grand Central Dispatch. I see merit in this because I agree with their document arguing that it's beneficial to let the system dynamically create and destroy threads as needed. A touch on dynamic thread pool will also be considered a bonus in this regard.

$\endgroup$
4
  • $\begingroup$ This will be my study subject for the coming months and I'll post my result when it concludes. I gratefully welcome all those that may provide insights. $\endgroup$
    – DannyNiu
    Aug 4 at 13:02
  • $\begingroup$ If the message is provided sequentially then it makes sense to use some kind of leaf sized window into the data in memory, which then gets put into a queue to be picked up by the next future / lightweight thread that is available. Then you can wait for each branch to finalize. This can still be put into some kind of an init / update / final scheme, with the disadvantage that the data provided during update is generally not protected against change (and you'd want that call to be asynchronous for it to work well). $\endgroup$
    – Maarten Bodewes
    Aug 4 at 13:28
  • $\begingroup$ I was also thinking of a callback mechanism, such as "give me the data starting at offset X and with (max) length L. But requiring full random access to the message data is probably even worse than assuming it is provided sequentially, so I don't think that's the way to go. $\endgroup$
    – Maarten Bodewes
    Aug 4 at 13:32
  • $\begingroup$ By the way, I should have some kind of parallel cipher (CTR) implementation where I rotate internal buffers and use those to control the number of futures. That could also be used for this kind of implementation. $\endgroup$
    – Maarten Bodewes
    Aug 4 at 13:39

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.