4 ms·
It's a tradeoff. In libc++'s version you still have string size stored in the top 7 bits so you just need a bitshift to get size. It sounds like fb's implementa
by fyp 7y ago
It's a tradeoff. In libc++'s version you still have string size stored in the top 7 bits so you just need a bitshift to get size. It sounds like fb's implementation would require looping until null terminator to get the size.
- edflsafoiewq 7y agoIIRC you store (23 - size) in the last byte in "small string" mode, so when the size gets to 23, the last byte is 0, doubling as the null terminator.
- lilyball 7y agoSurely it must be (23 - size) << 1, otherwise you won't guarantee a 0 in the LSB.
- edflsafoiewq 7y agoIf you use the LSB of the last byte for a flag, you're using the 56th bit of one of the {data,size,cap} words. I'd use the MSB in this case, since you can shift that off easier.
- SamReidHughes 7y agoOn little endian systems it uses two MSb's, on big endian systems it uses two LSb's. There are actually two flag bits.
- deleted 7y ago[deleted]
- roel_v 7y agoTo save those who, like me, were going to comment 'that would violate the standard because std::string::size is required to be O(1) complexity' a Google - the standard recommends but doesn't require that.
- coolplants 7y agoEven if the standard required O(1) it would conform because the loop is bounded (<= 23), it’s not O(n)
- epistasis 7y agoFacebook's implementation would still be constant time for short strings, because there's a constant which bounds the runtime. Though I hear that the definition of big-O notation has shifted a bit in Silicon Valley these days so maybe that answer would get me in trouble in an interview.
- ryani 7y agoIt's true that big-O notation only concerns behavior with large N, but it's a bit disingenuous to say that the loop executes a constant number of times -- by that argument, you could say that if you implemented size() by strlen() it's O(1) because the string must be less than 2^64 bytes long on a 64-bit machine. So I can see why someone would claim that implementing size() via strlen() "only" for small strings shouldn't be considered O(1), because strlen() is O(n) and within that class of strings the runtime is increasing as the length increases.
- coolplants 7y agoI think it’s a bit more disingenuous to compare the magnitudes of 2^64 and 23 for the sake of argument, as if 2^64 isn’t practically asymptotic.
- slavik81 7y agoTo be O(N), the time required for the lookup would have to continue to grow indefinitely. This has an upper bound.
- deleted 7y ago[deleted]
- deleted 7y ago[deleted]