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

41–50 of 62 posts

Re: Rapidstring: Maybe the fastest string library ever

#41

Post by masklinn »

JeromeBonnet wrote: post #40
masklinn wrote: post #36

Earlier quoted context omitted.

> 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.

> 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.

If you do that you have to spill your SSO to the heap way earlier, rapidstring would have 15 bytes SSO instead of the current 31, and std::string would be limited to 7 compared to the current 23~31.

Re: Rapidstring: Maybe the fastest string library ever

#42

Post by JeromeBonnet »

masklinn wrote: post #41
JeromeBonnet wrote: post #40

Earlier quoted context omitted.

> 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.

> 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. If you do that you have to spill your SSO to the heap way earlier, rapidstring would have 15 bytes SSO instead of the current 31, and std::string would be limited to 7 compared to the current 23~31.

It is a trade off. I see the length limit is 23 for SSO-23, but it could have been arbitrarily larger. What is the basis for the determination of those magic length limit targets?

Re: Rapidstring: Maybe the fastest string library ever

#43

Post by masklinn »

JeromeBonnet wrote: post #42
masklinn wrote: post #41

Earlier quoted context omitted.

> 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. If you do that you have to spill your SSO to the heap way earlier, rapidstring would have 15 bytes SSO instead of the current 31, and std::string would be limited to 7 compared to the current 23~31.

It is a trade off. I see the length limit is 23 for SSO-23, but it could have been arbitrarily larger. What is the basis for the determination of those magic length limit targets?

The size of the pre-existing non-SSO string. SSO-23 is predicated on a stack layout of (pointer, capacity, size) (as in Clang). That's why SSO-23 applied to the pre-existing MSVC or GCC std::string yields 31 on-stack bytes, they have a stack size of 32 bytes.

Re: Rapidstring: Maybe the fastest string library ever

#44

Post by iforgotpassword »

flohofwoe wrote: post #34
vbezhenar wrote: post #27

Earlier quoted context omitted.

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).

All winapi functions use UCS2. The "ASCII" versions are just wrappers that implicitly convert from the current locale (latin1, ShiftJIS, BIG5, ...) to UCS2. Try passing some Japanese text to the ASCII version of a function on a system that's set to eg. German and see what happens...

Re: Rapidstring: Maybe the fastest string library ever

#45

Post by iforgotpassword »

rurban wrote: post #38
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.

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…

Japanese is also great. While there are general rules when you use hiragana vs. katakana, sometimes for stylistic reasons the "wrong" one is used, or some kanji is "spelled out" as hiragana, and depending on context, you might or might not want to include these in your search results.

Tbh I just stopped caring and now happily live in my little world where utf8 is the solution to everything, doesn't yield any problems ever, and anyone telling me differently gets completely ignored.

Re: Rapidstring: Maybe the fastest string library ever

#46

Post by flohofwoe »

rurban wrote: post #39
whyever wrote: post #32

Earlier quoted context omitted.

> 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.

At least on Mac the command line utils support international text just fine, all text files are encoded as UTF-8 by convention, and (for instance) grep's case-insensitive search works for non-ASCII characters.

Re: Rapidstring: Maybe the fastest string library ever

#47

Post by flohofwoe »

iforgotpassword wrote: post #44
flohofwoe wrote: post #34

Earlier quoted context omitted.

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).

All winapi functions use UCS2. The "ASCII" versions are just wrappers that implicitly convert from the current locale (latin1, ShiftJIS, BIG5, ...) to UCS2. Try passing some Japanese text to the ASCII version of a function on a system that's set to eg. German and see what happens...

Most Win32 API functions don't even take string parameters, so there's no separate ASCII or UCS-2 version of those.

Of the functions that take strings, the old ...A() versions should never be called anyway since they depend on the obsolete concept of code pages. The proper way to work with strings on Windows (IMHO) is to encode all string data to UTF-8, only encode/decode from/to UCS-2 when needed, and call the ...W() functions explicitely (don't use the global UNICODE define).

Also see: http://utf8everywhere.org/

Re: Rapidstring: Maybe the fastest string library ever

#48

Post by twic »

JeromeBonnet wrote: post #40
masklinn wrote: post #36

Earlier quoted context omitted.

> 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.

I don't think it decreases the overall memory use of small strings - it just moves that use from the string struct to the character buffer. Bear in mind that in this design, the character buffer is never shared between multiple string structs; they each own their own separate buffer. If you want multiple references to the same string, you would use several pointers to a string struct, rather than having several string structs sharing the same buffer.

If you're coming from a GC'd language like Java, Ruby, etc, then there's a bit of a mindset shift around strings.

Re: Rapidstring: Maybe the fastest string library ever

#49

Post by burntsushi »

flohofwoe wrote: post #46
rurban wrote: post #39

Earlier quoted context omitted.

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.

At least on Mac the command line utils support international text just fine, all text files are encoded as UTF-8 by convention, and (for instance) grep's case-insensitive search works for non-ASCII characters.

It's the same on Linux. GNU grep supports Unicode just fine, assuming, of course, your system's locale settings are configured correctly. :-)

Re: Rapidstring: Maybe the fastest string library ever

#50

Post by sundarurfriend »

rurban wrote: post #37
flohofwoe wrote: post #33

Earlier quoted context omitted.

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 the…

How does the utf8proc[1] library that Julia uses compare to these?

[1] http://juliastrings.github.io/utf8proc/doc/

Post reply on HN