Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Rapidstring: Maybe the fastest string library ever

github.com

Post reply on HN
Print view View original

31–40 of 62 posts

Re: Rapidstring: Maybe the fastest string library ever

#31

Post by flohofwoe »

olliej wrote: post #8

I’d be more interested in “this is faster than X” claims if it does a fair comparison - pushing the implementation out of the header. Otherwise (depending on operation) inlining ends up significantly throwing off performance numbers. That said it’s much easier to make faster than libN string libraries if you don’t have abi constraints to deal with. This uses any value struct to hold much of its metadata which causes…

Whether a function body is implemented in a header or implementation source file doesn't matter much these days where LTO/LTCG is common. If the compiler/linker thinks a function is fit for inlining it will do so.

Re: Rapidstring: Maybe the fastest string library ever

#32

Post by whyever »

rurban wrote: post #3

I like the stack trick. But it's still just a membuf library, without any string support. No encoding, no Unicode, no upper/lower/fc/norm support, which would be important to compare or find strings. And coreutils (e.g grep) still have no unicode support. It's 2018, not the seventies anymore. Unicode strings need to be normalized to be able to be found.

> But it's still just a membuf library, without any string support.

Just like the strings in the C and C++ standard library.

Re: Rapidstring: Maybe the fastest string library ever

#33

Post by flohofwoe »

lifthrasiir wrote: post #22
johnboyer wrote: post #16

Earlier quoted context omitted.

Unicode is supported with UTF-8, only different character types aren't supported because generics are messy in C. I thought of accepting void* to support wchar_t and others, but some performance penalties came with it so I decided against it.

No, having different character types (I believe you are referring to C11's `char16_t` and `char32_t`?) is not a requirement for Unicode support. At the very least you need to have a single function or two that... * Receives a string expected to be encoded in UTF-8, and an offset to it expected to be a UTF-8 sequence boundary. * Scans forward or backward for the next or previous UTF-8 sequence boundary. * Optionally r…

I don't see any functions in the OP's library that would require dedicated UTF-8 handling. The string length is given in bytes, not characters or codepoints. There's no functionality to give you the character at n-th location etc... you can easily implement all UNICODE-specific functionality in a separate library and use it together with the OPs library. IMHO that's even preferable.

Re: Rapidstring: Maybe the fastest string library ever

#34

Post by flohofwoe »

vbezhenar wrote: post #27
dwheeler wrote: post #24

Earlier quoted context omitted.

It appears to support Unicode just fine, you just have to use UTF-8. I find that in most cases you should only use UTF-8 anyway, so in most cases that is not a problem.

If you're using WinAPI, you have to use UCS-16. Converting strings for every call would be abysmal to performance.

There are only very few WinAPI functions which use UCS-2 vs ASCII, and none of them are performance-critical. It's totally fine to convert from/to UTF-8 on the fly, especially since the conversion is extremely cheap (and the rest of the world has moved on to UTF-8 anyway).

Re: Rapidstring: Maybe the fastest string library ever

#36

Post by masklinn »

JeromeBonnet wrote: post #35

Hi, John! Why did you chose to store 'size' and 'capacity' in the 'rs_heap' struct instead of at the beginning of the heap-allocated buffer pointed to by 'buffer'? Did you find it was preferable to have a larger 'rs_heap'?

> Why did you chose to store 'size' and 'capacity' in the 'rs_heap' struct instead of at the beginning of the heap-allocated buffer pointed to by 'buffer'?

Why would you store the size and capacity as part of the buffer? It makes the buffer more complex (you need a separate unsized struct or some mess special-casing the first 16 bytes or so), wastes heap size, requires dereferencing before you can even check on size & capacity, and makes SSO harder/more limited.

AFAIK both C++'s std::string and Rust's String store size and capacity on the stack, separate from the buffer.

Re: Rapidstring: Maybe the fastest string library ever

#37

Post by rurban »

flohofwoe wrote: post #33
lifthrasiir wrote: post #22

Earlier quoted context omitted.

No, having different character types (I believe you are referring to C11's `char16_t` and `char32_t`?) is not a requirement for Unicode support. At the very least you need to have a single function or two that... * Receives a string expected to be encoded in UTF-8, and an offset to it expected to be a UTF-8 sequence boundary. * Scans forward or backward for the next or previous UTF-8 sequence boundary. * Optionally r…

I don't see any functions in the OP's library that would require dedicated UTF-8 handling. The string length is given in bytes, not characters or codepoints. There's no functionality to give you the character at n-th location etc... you can easily implement all UNICODE-specific functionality in a separate library and use it together with the OPs library. IMHO that's even preferable.

Yes, but don't call it string library then. Strings should handle strings, and strings are unicode now. Unicode needs to be normalized and needs case-insensitive support.

And it's not easy. I implemented the third of its kind. First there was ICU, which is overly bloated. You don't need 30MB for a simple string libc. Then there is libunistring which has overly slow iterators, so not usable for coreutils. And then there's my safelibc, which is small and fast, but only for wide-chars, not utf-8.

I fixed and updated the musl case-mapping, making it 2x faster, but this is not in yet. And there's not even a properly spec'ed wcscmp/wcsicmp to find strings. glibc is an overall mess. I won't touch that. wcsicmp/wcsfc/wcsnorm are not even in POSIX.

Re: Rapidstring: Maybe the fastest string library ever

#38

Post by rurban »

dwheeler wrote: post #24
MrEldritch wrote: post #9

Earlier quoted context omitted.

In the modern development environment, I think it's genuinely fair to say that something which doesn't support Unicode strings cannot be claimed to support strings. It's like saying you have the fastest integer math library ever written, with the minor caveat that it only supports numbers smaller than 256 because it achieves that speed by being simply a hardcoded lookup table, and crashes if you give it anything else…

It appears to support Unicode just fine, you just have to use UTF-8. I find that in most cases you should only use UTF-8 anyway, so in most cases that is not a problem.

Nope, big mistake. You cannot just search for "Café" in "Café", as there are multiple representations for the same character. Think of Cyrillic vs Greek, Han vs Hangul. The popular garbage-in, garbage-out doesn't apply to unicode identifiers. That's why the Mac filesystem normalization was correct, and the unix filesystems are all broken. If it's not identifiable it's no identifier. That's why java and cperl are the only languages with proper and safe unicode support. Python 3 is a bit better than Python 2, Perl6 better than Perl5 and the rest, but still don't apply unicode security guidelines for identifiers. It's much better for browsers and email clients.

And with case-insensitivity it gets worse, as there are some locale dependent additional rules, for Turkish and Lithuania. And this depends on "some" global settings.

http://perl11.org/blog/foldcase.html

Re: Rapidstring: Maybe the fastest string library ever

#39

Post by rurban »

whyever wrote: post #32
rurban wrote: post #3

I like the stack trick. But it's still just a membuf library, without any string support. No encoding, no Unicode, no upper/lower/fc/norm support, which would be important to compare or find strings. And coreutils (e.g grep) still have no unicode support. It's 2018, not the seventies anymore. Unicode strings need to be normalized to be able to be found.

> But it's still just a membuf library, without any string support. Just like the strings in the C and C++ standard library.

Exactly. POSIX and the C/C++ standards don't support strings and utf-8 yet neither. coreutils and grep neither. Most computer languages neither.

It's a mess and a big security risk. We are still in the stone age of string support.

Re: Rapidstring: Maybe the fastest string library ever

#40

Post by JeromeBonnet »

masklinn wrote: post #36
JeromeBonnet wrote: post #35

Hi, John! Why did you chose to store 'size' and 'capacity' in the 'rs_heap' struct instead of at the beginning of the heap-allocated buffer pointed to by 'buffer'? Did you find it was preferable to have a larger 'rs_heap'?

> Why did you chose to store 'size' and 'capacity' in the 'rs_heap' struct instead of at the beginning of the heap-allocated buffer pointed to by 'buffer'? Why would you store the size and capacity as part of the buffer? It makes the buffer more complex (you need a separate unsized struct or some mess special-casing the first 16 bytes or so), wastes heap size, requires dereferencing before you can even check on size…

> Why would you store the size and capacity as part of the buffer?

To decrease the memory footprint of your small strings. It can see how some uses cases where a large proportion of strings are very small would benefit from it.

I was just curious to know if that design decision was based on analysis of a real use case, or if it was due to a compatibility issue or something.

Post reply on HN