Yet another binary reader (10x faster than Hackage's binary; )
I was investigating Haskell’s binary serialization libraries and has found that lot of them (binary, cereal and protocol-buffers) has pretty similar design. They capable to consume lazy bytestrings and either produce result, report error or produce partial result, indicating that more input data required. Such design leads to quite complex readers, and often ends up with producing closures in runtime. If you take a close look at binary’s microbenches (binary in general bit faster than cereal, so I focused on binary) you will discover, that it triggers GC even during simple tasks, such as reading a bunch of Word64 and summing results. And it relatively slow. Binary’s performance limited to hundreds of megabytes per second even in simple scenarios, but actual memory bandwidth should allow us process gigabytes per second. So, I decided to try a different approach. My approach is based on two assumptions so if it does not suit your case it obliviously will not work for you. First – when dealing with binary data we always know exactly how many bytes we want to read. This happens because we either read a fixed size primitive type or length-prefixed variable size data (possibly not “prefixed”, but you always know expected message length from somewhere). Second – chunks of data are continuous. I.e. we working with strict bytestrings more often. Even when you processing chunked stream of data with unknown number of messages (such as Mesos RecordIO Format) you should always be able to allocate continuous memory buffer for a single entity you want to deserialize. If it’s ok for you lets go on. First thing I’ve created was so called static reader. Static – because reader knows how mush bytes it wants to consume at compile time. Such readers suitable for reading combinations of primitive values. Here the implementation https://github.com/PROTEINE-INSAIDERS/lev-tolstoy/blob/master/src/Lev/Reader... Static reader is somewhat monadic (you can use do-syntax with RebindableSyntax extension like here https://github.com/PROTEINE-INSAIDERS/lev-tolstoy/blob/master/bench/Bench/Le... ) but it actually indexed monad and it unfortunately incompatible with traditional monads. Offsets and sizes are calculates at type level during the compile time and according to microbences static reader does not introduced any overhead compared to hand-written reader using the low-level indexInt64OffAddr# function ( https://github.com/PROTEINE-INSAIDERS/lev-tolstoy/blob/master/bench/Bench/Ha... ) Next thing was a dynamic reader. Dynamic readers are composed from static readers, they are fully monadic and allow you to read length-prefixed data structures (you read length with wrapped static reader and then perform normal monadic binding to supply a reader which reads a value). Here the implementation https://github.com/PROTEINE-INSAIDERS/lev-tolstoy/blob/master/src/Lev/Reader... I’ve discovered, that typeclasses are surprisingly fast. So, it’s completely ok to have something like “(Cursor c) => … Reader” where cursor contains functions for overflow checking and memory buffer progression. I was not able to achieve same performance when I passed buffer callbacks explicitly, possibly because of inlining of specialization magic. So, I've created ByteStringCursor ( https://github.com/PROTEINE-INSAIDERS/lev-tolstoy/blob/master/src/Lev/Reader... ) which allows to read strict bytestrings. I suppose that cursors introduce flexibility: you may read strict bytestring or you may define custom cursor for reading custom memory buffers. Finally, I’ve written some microbenches for my cases and also ported one microbench from binary. And my implementation was able to run 10x-15x faster than binary on strict bytestring. Moreover, it does not trigger GC during the run at all! You may find the project and all the benches here https://github.com/PROTEINE-INSAIDERS/lev-tolstoy So, what's the purpose of my message? It’s quite unlikely that I’ll release my code on the Hackage. This is because I’m a hobbyist Haskell developer and doing it all in my free time. But before mr. Putin will close Internet in Russia I’d like to demonstrate that it’s possible to write very fast binary deserializer taking in account several assumptions which seems quite reasonably for me. So, feel free to borrow the ideas, or share the ideas, if you know how it could be implemented better. -- Sincerely, Stanislav Chernichkin.
Sounds fascinating.
I don't currently have a strong need for a fast binary serialiser but your
explorations inside the GHC optimiser sound very interesting.
If you can get around to doing a blog/presentation on your explorations and
techniques I'll sure be interested and I'm sure would be many in the
Haskell community.
On Wed, Mar 20, 2019 at 8:58 AM Станислав Черничкин
I was investigating Haskell’s binary serialization libraries and has found that lot of them (binary, cereal and protocol-buffers) has pretty similar design. They capable to consume lazy bytestrings and either produce result, report error or produce partial result, indicating that more input data required. Such design leads to quite complex readers, and often ends up with producing closures in runtime. If you take a close look at binary’s microbenches (binary in general bit faster than cereal, so I focused on binary) you will discover, that it triggers GC even during simple tasks, such as reading a bunch of Word64 and summing results. And it relatively slow. Binary’s performance limited to hundreds of megabytes per second even in simple scenarios, but actual memory bandwidth should allow us process gigabytes per second. So, I decided to try a different approach.
My approach is based on two assumptions so if it does not suit your case it obliviously will not work for you.
First – when dealing with binary data we always know exactly how many bytes we want to read. This happens because we either read a fixed size primitive type or length-prefixed variable size data (possibly not “prefixed”, but you always know expected message length from somewhere).
Second – chunks of data are continuous. I.e. we working with strict bytestrings more often. Even when you processing chunked stream of data with unknown number of messages (such as Mesos RecordIO Format) you should always be able to allocate continuous memory buffer for a single entity you want to deserialize.
If it’s ok for you lets go on. First thing I’ve created was so called static reader. Static – because reader knows how mush bytes it wants to consume at compile time. Such readers suitable for reading combinations of primitive values. Here the implementation https://github.com/PROTEINE-INSAIDERS/lev-tolstoy/blob/master/src/Lev/Reader... Static reader is somewhat monadic (you can use do-syntax with RebindableSyntax extension like here https://github.com/PROTEINE-INSAIDERS/lev-tolstoy/blob/master/bench/Bench/Le... ) but it actually indexed monad and it unfortunately incompatible with traditional monads. Offsets and sizes are calculates at type level during the compile time and according to microbences static reader does not introduced any overhead compared to hand-written reader using the low-level indexInt64OffAddr# function ( https://github.com/PROTEINE-INSAIDERS/lev-tolstoy/blob/master/bench/Bench/Ha... )
Next thing was a dynamic reader. Dynamic readers are composed from static readers, they are fully monadic and allow you to read length-prefixed data structures (you read length with wrapped static reader and then perform normal monadic binding to supply a reader which reads a value). Here the implementation https://github.com/PROTEINE-INSAIDERS/lev-tolstoy/blob/master/src/Lev/Reader...
I’ve discovered, that typeclasses are surprisingly fast. So, it’s completely ok to have something like “(Cursor c) => … Reader” where cursor contains functions for overflow checking and memory buffer progression. I was not able to achieve same performance when I passed buffer callbacks explicitly, possibly because of inlining of specialization magic. So, I've created ByteStringCursor ( https://github.com/PROTEINE-INSAIDERS/lev-tolstoy/blob/master/src/Lev/Reader... ) which allows to read strict bytestrings. I suppose that cursors introduce flexibility: you may read strict bytestring or you may define custom cursor for reading custom memory buffers.
Finally, I’ve written some microbenches for my cases and also ported one microbench from binary. And my implementation was able to run 10x-15x faster than binary on strict bytestring. Moreover, it does not trigger GC during the run at all! You may find the project and all the benches here https://github.com/PROTEINE-INSAIDERS/lev-tolstoy
So, what's the purpose of my message? It’s quite unlikely that I’ll release my code on the Hackage. This is because I’m a hobbyist Haskell developer and doing it all in my free time. But before mr. Putin will close Internet in Russia I’d like to demonstrate that it’s possible to write very fast binary deserializer taking in account several assumptions which seems quite reasonably for me. So, feel free to borrow the ideas, or share the ideas, if you know how it could be implemented better.
-- Sincerely, Stanislav Chernichkin. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.
I will enjoy learning more about optimization in Haskell from this repo.
Thanks for writing (it and your email)!
Ryan Reich
On Tue, Mar 19, 2019, 14:58 Станислав Черничкин
I was investigating Haskell’s binary serialization libraries and has found that lot of them (binary, cereal and protocol-buffers) has pretty similar design. They capable to consume lazy bytestrings and either produce result, report error or produce partial result, indicating that more input data required. Such design leads to quite complex readers, and often ends up with producing closures in runtime. If you take a close look at binary’s microbenches (binary in general bit faster than cereal, so I focused on binary) you will discover, that it triggers GC even during simple tasks, such as reading a bunch of Word64 and summing results. And it relatively slow. Binary’s performance limited to hundreds of megabytes per second even in simple scenarios, but actual memory bandwidth should allow us process gigabytes per second. So, I decided to try a different approach.
My approach is based on two assumptions so if it does not suit your case it obliviously will not work for you.
First – when dealing with binary data we always know exactly how many bytes we want to read. This happens because we either read a fixed size primitive type or length-prefixed variable size data (possibly not “prefixed”, but you always know expected message length from somewhere).
Second – chunks of data are continuous. I.e. we working with strict bytestrings more often. Even when you processing chunked stream of data with unknown number of messages (such as Mesos RecordIO Format) you should always be able to allocate continuous memory buffer for a single entity you want to deserialize.
If it’s ok for you lets go on. First thing I’ve created was so called static reader. Static – because reader knows how mush bytes it wants to consume at compile time. Such readers suitable for reading combinations of primitive values. Here the implementation https://github.com/PROTEINE-INSAIDERS/lev-tolstoy/blob/master/src/Lev/Reader... Static reader is somewhat monadic (you can use do-syntax with RebindableSyntax extension like here https://github.com/PROTEINE-INSAIDERS/lev-tolstoy/blob/master/bench/Bench/Le... ) but it actually indexed monad and it unfortunately incompatible with traditional monads. Offsets and sizes are calculates at type level during the compile time and according to microbences static reader does not introduced any overhead compared to hand-written reader using the low-level indexInt64OffAddr# function ( https://github.com/PROTEINE-INSAIDERS/lev-tolstoy/blob/master/bench/Bench/Ha... )
Next thing was a dynamic reader. Dynamic readers are composed from static readers, they are fully monadic and allow you to read length-prefixed data structures (you read length with wrapped static reader and then perform normal monadic binding to supply a reader which reads a value). Here the implementation https://github.com/PROTEINE-INSAIDERS/lev-tolstoy/blob/master/src/Lev/Reader...
I’ve discovered, that typeclasses are surprisingly fast. So, it’s completely ok to have something like “(Cursor c) => … Reader” where cursor contains functions for overflow checking and memory buffer progression. I was not able to achieve same performance when I passed buffer callbacks explicitly, possibly because of inlining of specialization magic. So, I've created ByteStringCursor ( https://github.com/PROTEINE-INSAIDERS/lev-tolstoy/blob/master/src/Lev/Reader... ) which allows to read strict bytestrings. I suppose that cursors introduce flexibility: you may read strict bytestring or you may define custom cursor for reading custom memory buffers.
Finally, I’ve written some microbenches for my cases and also ported one microbench from binary. And my implementation was able to run 10x-15x faster than binary on strict bytestring. Moreover, it does not trigger GC during the run at all! You may find the project and all the benches here https://github.com/PROTEINE-INSAIDERS/lev-tolstoy
So, what's the purpose of my message? It’s quite unlikely that I’ll release my code on the Hackage. This is because I’m a hobbyist Haskell developer and doing it all in my free time. But before mr. Putin will close Internet in Russia I’d like to demonstrate that it’s possible to write very fast binary deserializer taking in account several assumptions which seems quite reasonably for me. So, feel free to borrow the ideas, or share the ideas, if you know how it could be implemented better.
-- Sincerely, Stanislav Chernichkin. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.
Am 19.03.19 um 22:58 schrieb Станислав Черничкин:
possibly because of inlining of specialization magic.
I have seen people validate this kind of assumption, by looking at the various intermediate representations of code. If you're after performance, you may want to do that. You may find that things work differently than expected, with the potential for becoming a bottleneck when stuff is scaled up (more varied datatypes in the input stream, or more complex target datatypes, stuff hidden behind "oh I don't need GC yet", that kind of finding). Regards, Jo
Recently I found http://hackage.haskell.org/package/store which I missed
during my previous investigation. It based on same principles and runs at
same speed as my prototype. And it ready-to-use. It seems I just reinvented
what was done before by FP Complete :)
ср, 20 мар. 2019 г. в 00:58, Станислав Черничкин
I was investigating Haskell’s binary serialization libraries and has found that lot of them (binary, cereal and protocol-buffers) has pretty similar design. They capable to consume lazy bytestrings and either produce result, report error or produce partial result, indicating that more input data required. Such design leads to quite complex readers, and often ends up with producing closures in runtime. If you take a close look at binary’s microbenches (binary in general bit faster than cereal, so I focused on binary) you will discover, that it triggers GC even during simple tasks, such as reading a bunch of Word64 and summing results. And it relatively slow. Binary’s performance limited to hundreds of megabytes per second even in simple scenarios, but actual memory bandwidth should allow us process gigabytes per second. So, I decided to try a different approach.
My approach is based on two assumptions so if it does not suit your case it obliviously will not work for you.
First – when dealing with binary data we always know exactly how many bytes we want to read. This happens because we either read a fixed size primitive type or length-prefixed variable size data (possibly not “prefixed”, but you always know expected message length from somewhere).
Second – chunks of data are continuous. I.e. we working with strict bytestrings more often. Even when you processing chunked stream of data with unknown number of messages (such as Mesos RecordIO Format) you should always be able to allocate continuous memory buffer for a single entity you want to deserialize.
If it’s ok for you lets go on. First thing I’ve created was so called static reader. Static – because reader knows how mush bytes it wants to consume at compile time. Such readers suitable for reading combinations of primitive values. Here the implementation https://github.com/PROTEINE-INSAIDERS/lev-tolstoy/blob/master/src/Lev/Reader... Static reader is somewhat monadic (you can use do-syntax with RebindableSyntax extension like here https://github.com/PROTEINE-INSAIDERS/lev-tolstoy/blob/master/bench/Bench/Le... ) but it actually indexed monad and it unfortunately incompatible with traditional monads. Offsets and sizes are calculates at type level during the compile time and according to microbences static reader does not introduced any overhead compared to hand-written reader using the low-level indexInt64OffAddr# function ( https://github.com/PROTEINE-INSAIDERS/lev-tolstoy/blob/master/bench/Bench/Ha... )
Next thing was a dynamic reader. Dynamic readers are composed from static readers, they are fully monadic and allow you to read length-prefixed data structures (you read length with wrapped static reader and then perform normal monadic binding to supply a reader which reads a value). Here the implementation https://github.com/PROTEINE-INSAIDERS/lev-tolstoy/blob/master/src/Lev/Reader...
I’ve discovered, that typeclasses are surprisingly fast. So, it’s completely ok to have something like “(Cursor c) => … Reader” where cursor contains functions for overflow checking and memory buffer progression. I was not able to achieve same performance when I passed buffer callbacks explicitly, possibly because of inlining of specialization magic. So, I've created ByteStringCursor ( https://github.com/PROTEINE-INSAIDERS/lev-tolstoy/blob/master/src/Lev/Reader... ) which allows to read strict bytestrings. I suppose that cursors introduce flexibility: you may read strict bytestring or you may define custom cursor for reading custom memory buffers.
Finally, I’ve written some microbenches for my cases and also ported one microbench from binary. And my implementation was able to run 10x-15x faster than binary on strict bytestring. Moreover, it does not trigger GC during the run at all! You may find the project and all the benches here https://github.com/PROTEINE-INSAIDERS/lev-tolstoy
So, what's the purpose of my message? It’s quite unlikely that I’ll release my code on the Hackage. This is because I’m a hobbyist Haskell developer and doing it all in my free time. But before mr. Putin will close Internet in Russia I’d like to demonstrate that it’s possible to write very fast binary deserializer taking in account several assumptions which seems quite reasonably for me. So, feel free to borrow the ideas, or share the ideas, if you know how it could be implemented better.
-- Sincerely, Stanislav Chernichkin.
-- Sincerely, Stanislav Chernichkin.
participants (4)
-
Clinton Mead -
Joachim Durchholz -
Ryan Reich -
Станислав Черничкин