3 ms·
Please don't design bit/byte string libraries until you understand how Erlang handles them, because that language has by far the best support. https://www.erla
by rwmj 4y ago
Please don't design bit/byte string libraries until you understand how Erlang handles them, because that language has by far the best support. https://www.erlang.org/doc/programming_examples/bit_syntax.html https://www.erlang.org/doc/programming_examples/bit_syntax.h...
Here's my OCaml library influenced heavily by Erlang: https://bitstring.software/examples/ https://bitstring.software/examples/
- brobinson 4y agoI think the author of ripgrep knows a thing or two about processing bits and bytes.
- CodesInChaos 4y agoYour links seems to use string as a synonym of sequence. The linked crate is about strings which represent text, and many of them assume that the encoding is a superset of ASCII, and some ever assume it's potentially invalid UTF-8. So I don't see how your links are relevant here.
- rwmj 4y agoIt deals with both bits and byte strings, and as it's implemented as a set of compile-time macros there's no overhead as long as the compiler can easily see that the string is byte-aligned.
- lifthrasiir 4y agoYou have solved a different problem. The OP benchmarks grep and wc as motivating examples; how does your library (and the Erlang design in general) help in such cases?
- speed_spread 4y agoIt feels like you didn't read the linked article and are only using the title to plug your lib. Without discussing the relative merits of your work, _you_ might have to learn a thing or two about self-promotion opportunities. Step 1: "understand what people are talking about before participating". Amazingly, this actually applies to all conversations.
- burntsushi 4y agoCan you say what is specifically wrong with bstr (while tying it to real world use cases) instead of trying to tell me what I do or don't understand?
- zozbot234 4y agoMuch of it has seemingly no reason for being specialized to u8, especially the needle/haystack search example that takes up much of the blogpost. Even the "replacing invalid UTF-8 with the generic replacement character" part could simply be factored out as an iterator adapter on u8's.
- burntsushi 4y agoI think that would be an interesting API design to explore, absolutely. I think you'll have a lot of issues making it fast though. There is a fair bit of SIMD going on under the hoods in both the substring routines and the UTF-8 validation routines, for example. Building APIs based around iterator adapters that munch one byte at a time are difficult to square with SIMD optimizations that want to operate on a whole bunch of bytes at a time. Consider, for example, how you might use a routine like memchr[1] if all of your public APIs are generic iterator adapters. And then once you get into things like regex engines, modifying them to work on Iterator<Item=u8> is a highly non-trivial affair. It is of course possible to write a regex engine that works on such things, but it's going to be limited in performance or capabilities. The way to make regexes and streaming work together is probably something more like Iterator<Item=&[u8]> (which is perhaps roughly analogous to what Hyperscan does). You really want blocks of bytes, not one-byte-at-a-time. [1]: https://github.com/BurntSushi/memchr/blob/8037d11b4357b0f07be2bb66dc2659d9cf28ad32/src/memchr/x86/sse2.rs#L16 https://github.com/BurntSushi/memchr/blob/8037d11b4357b0f07b...
- gpm 4y agoUTF-8 by definition is a sequence of u8's, what would you like it to be generic over, and how would that help anyone!?
- gliptic 4y agoIt's specialized to &[u8] in order to supply optimized implementations.
- Dr_Emann 4y agoHonestly feels like a very, very different use case from utf8-ish strings, at a quick read?
- bsder 4y agoThis library isn't about bit packing--it's mostly about optimizing text and presumably "ripgrep" which the author is also the creator of. However, I do agree that Erlang's Bit Syntax is, by far, the best handling I've ever seen for slicing and dicing bits and bytes at the very lowest level.
- throwawaymaths 4y agoErlang's bit syntax is actually kind of broken: See if you can guess correctly what this produces: <<1:5, 2:4, 0xFFOO:15, "foo":binary>>
- rkangel 4y agoThe correct answer to this is actually "syntax error" because your `0xFFOO:15` has got two letter O's in it and anyway 0xFF00 isn't valid erlang (no hex literals). If you mean this equivalent bit of Elixir, then I got it right: <<1::5, 2::4, 0xFFOO::15, "foo"::binary>> I think it's all good and sensible, except that "0xFF00::15" should raise an error. The bit syntax silently masks out some stuff which can hide some errors.
- throwawaymaths 4y agoYeah, sorry typing on phone. Ok. Maybe I'm just dumb. But I was really surprised that the bit order goes from msbit to lsbit (while the byte order goes from lsbyte to msbyte). Since the 15 bit element crosses over the byte boundary (and overflows it) the arrangement -- 00s in byte 1 and 0x80 0x3F in bytes 2 and 3... is not obvious, to me). In particular this makes it tricky to reinterpret packed structs coming from c, when using NIFs Specifically, what I would have wanted, was lsb-msb in bytes, and an overflow error, or syntax in the descriptor modifier that is required if you might overflow. Or, this would all be solved if we used an RTL layouts like the divine one intended.
- rkangel 4y agoThe important thing to remember, it's just a sequence of bits (and if that's a multiple of 8 then you can look at it as a sequence of bytes instead). Byte boundaries are just a way of looking at the result. You get the bits in the order you ask for in the expression, and then it encodes each valuee as you ask. Note that the default encoding is big endian, so the value 0xFF00 comes out as the bit sequence 1111111100000000 wherever it is. Now converting from a C-struct you absolutely do have to think about byte order, but erlang has you there too. Let's say you've got this: #pragma pack(1) struct { uint16_t a; uint8_t b; uint8_t c; uint32_t d; }; Then all you do is: <<a::16-native, b::8, c::8, d::32-native>> = my_block_of_data And then all of your values (a, b, c, d) will be correct. As I said above, erlang defaults to encoding/decoding each value as big-endian (e.g. <<0xFF00::16>> is equivalent to <<0xFF00::16-big>>. This is the default because big endian is used for the vast majority of comms protocols (in that context it's also called 'network byte order'). When interpreting values in memory though it can be either, depending on your processor (although mostly -little these days). Using -native as yoru endianness means "use big or little as appropriate for my processor". It's also a good signal that you're interpreting something from memory (as supposed to a protocol).