HN Explorer

21 comments

[ 4.5 ms ] story [ 40.7 ms ] thread
tyingq
Sds from Antirez has a lot of the same features (not all), and is kept updated since it's used by redis and other projects. https://github.com/antirez/sds/blob/master/README.md

Vstr appears to have last been updated in 2006. It does have a comparison of different string libraries, though that's also dated: http://www.and.org/vstr/comparison

cowsandmilk
SDS and this library are implemented completely differently...
endorphone
"Vstr" seems to target zero-copy by storing a string as a collection of blocks of data. Sds, from my reading, is essentially Pascal strings for C.

They don't seem to be comparable.

tyingq
It also targets "string like buffers" with arbitrary nulls, appends, splitting on a delimiter, and tokenizing. Yes, it works differently, and isn't readv/writev centric.
bvrmn
SDS has no special primitives to support scatter/gather io. In this regard sds-strings are the same as plain c-strings.
optimuspaul
2006 being the last update makes me not want to use it. But I suspect it is a stable library that doesn't need much update. I'm just getting back into c/c++ development and I'm very interested in libraries like these.
robobro
> 2006 being the last update makes me not want to use it. Why
optimuspaul
security concerns, might be unfounded, but something to consider
coliveira
C is an old language, some of the best libraries are stable for 20 years now.
joosters
Are these claims of O(1) behavior accurate? They might not be O(n), where n is the length of the string, but they sound likely to be O(v), where v is the number of 'iovec chunks' that the string is using (which could get large, depending upon how you are building up your strings)
kevingadd
If your strings are short that's basically O(1), which could be nice for some workloads - enums, json keys, etc.
jacwah
That's not what O(1) means. If your strings are short, complexity doesn't matter either way.
admax88q
That's still misleading.

If all my input is small then O(n^2) is basically O(1) as well.

leetcrew
if all your strings are of size < c, you can do any string operation on a single string in constant time.
saagarjha
There are certain (randomized) operations that you can’t…
naniwaduni
Everything is O(1) when you have finite bounded input.
chalst
If the list of chunks is represented as a deque, then concatenation and popping the first character can both be done in constant time.
joosters
Sure, but the page O(1) examples are:

1) Getting the data for a writev() call: Sure, it’s just returning a pointer to an array of iovecs, but someone is going to have to linearly scan that array.

2) Substituting or moving data anywhere in the string: As you say, you can do stuff with the start or end of a (v)string with O(1) but anywhere else will require a linear walk of the data chunks

chalst
If the claim is random access, then I agree that O(1) is imposssible. Rope would allow these tasks to be carried out in logarithmic time.

The tasks I chose were the first two API desiderata from http://www.and.org/vstr/design - which is the examples page you had in mind?

joosters
I was quoting from the ‘about’ section of the linked page. I’m not deliberately trying to pick on or criticise this data structure, it’s certainly a good way of manipulating some forms of text (I’ve used similar data structures for efficient HTTP processing/mangling). It’s just that there can be hidden costs and the O(1) claims appeared misleading.