Vstr: C string library designed to work optimally with vector I/O | Hacker News Reader

Vstr: C string library designed to work optimally with vector I/O

and.org

99 pointslelf21 comments

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

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

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.

SDS has no special primitives to support scatter/gather io. In this regard sds-strings are the same as plain c-strings.

I mentioned that.

SDS and this library are implemented completely differently...

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.

C is an old language, some of the best libraries are stable for 20 years now.

> 2006 being the last update makes me not want to use it. Why

security concerns, might be unfounded, but something to consider

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)

If the list of chunks is represented as a deque, then concatenation and popping the first character can both be done in constant time.

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

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?

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.

If your strings are short that's basically O(1), which could be nice for some workloads - enums, json keys, etc.

That's not what O(1) means. If your strings are short, complexity doesn't matter either way.

if all your strings are of size < c, you can do any string operation on a single string in constant time.

There are certain (randomized) operations that you can’t…

That's still misleading.

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

Everything is O(1) when you have finite bounded input.

Reply on news.ycombinator.com