5 ms·

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

99 points by lelf 7y ago

tyingq 7y ago
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 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 http://www.and.org/vstr/comparison
- cowsandmilk 7y ago
  SDS and this library are implemented completely differently...
- endorphone 7y ago
  "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 7y ago
    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 7y ago
      SDS has no special primitives to support scatter/gather io. In this regard sds-strings are the same as plain c-strings.
      - tyingq 7y ago
        I mentioned that.
- optimuspaul 7y ago
  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 7y ago
    > 2006 being the last update makes me not want to use it. Why
    - optimuspaul 7y ago
      security concerns, might be unfounded, but something to consider
  - coliveira 7y ago
    C is an old language, some of the best libraries are stable for 20 years now.
joosters 7y ago
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)
- chalst 7y ago
  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 7y ago
    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 7y ago
      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 http://www.and.org/vstr/design - which is the examples page you had in mind?
      - joosters 7y ago
        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.
- kevingadd 7y ago

99 points by lelf 7y ago

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 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 http://www.and.org/vstr/comparison

cowsandmilk 7y ago
SDS and this library are implemented completely differently...
endorphone 7y ago
"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 7y ago
  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 7y ago
    SDS has no special primitives to support scatter/gather io. In this regard sds-strings are the same as plain c-strings.
    - tyingq 7y ago
      I mentioned that.
optimuspaul 7y ago
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 7y ago
  > 2006 being the last update makes me not want to use it. Why
  - optimuspaul 7y ago
    security concerns, might be unfounded, but something to consider
- coliveira 7y ago
  C is an old language, some of the best libraries are stable for 20 years now.

joosters 7y ago

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)

chalst 7y ago
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 7y ago
  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 7y ago
    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 http://www.and.org/vstr/design - which is the examples page you had in mind?
    - joosters 7y ago
      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.
kevingadd 7y ago