11–20 of 22 posts
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)
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
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.
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
Earlier quoted context omitted.
"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.
Earlier quoted context omitted.
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.
Earlier quoted context omitted.
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
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?
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
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.
Earlier quoted context omitted.
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?
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 your strings are short that's basically O(1), which could be nice for some workloads - enums, json keys, etc.
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
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.