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, 2022 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, 2022 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, 2022 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, 2022 at 13:39

1 Answer 1

0
$\begingroup$

Data Availability

This is probably the least of the concerns. If data is available at a (much) slower rate than the hash algorithm implementation, then that's not the bottleneck.

System Load

This is a real concern, but not a major one. Any programmer with competent skill to do concurrent programming can write codes that're efficient in this respect.

Later Segments Arriving Early

There's probably no good solution to this. No boundedly capable system can handle infinitely many out-of-order data segments.

API Design

Paradigm for the Concurrent Object

Most concurrent APIs nowadays have the async-await semantics, which is straightforward, they're also good fit for the dispatch-like model. Most thread-poolling APIs also have the "async" part, but not necessarily the "await" part.

This is why, in my experiment, I chosed an "enqueue-await" approach, where

  • the enqueue operation puts a job into the thread pool,
  • the await operation waits for, not a specific one, but all currently queued jobs.

I've also listed some undefined behaviors that callers must avoid.

API Design for the Hashing Implementation

For a demonstration, see this

The initialization function stays as usual. It's functionality isn't changed in a noticable way from its single-threaded counterparts.

The update function now takes an instance of the said concurrent object, so that it can be invoked to exploit the thread-level parallelism on the host platform.

The finalization function is now different. Before this, single-threaded finalization functions takes the hashing context, compute the final digest, and sets some finalization guard to prevent it from being finalized again.

But with parallel and tree hashing, there're potentially data left in the working context that're not yet hashed because the update function had not been able to determined that as necessary. Therefore, the finalization function now also takes the instance of concurrent object.

Finally, we have a specialized read function. For many traditional hash functions, the "digest reading" function typically reads the hash digest from the start. However, most of the parallel and tree hashing functions we've encountered so far are actually XOFs. To allow for them to be read in both ways, I added a "flags" parameter to the read function, currently supporting only a "rewind" flag.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.