Adjust sds types#502
Conversation
Codecov ReportAttention: Patch coverage is
Additional details and impacted files@@ Coverage Diff @@
## unstable #502 +/- ##
============================================
+ Coverage 70.17% 70.26% +0.08%
============================================
Files 109 109
Lines 59904 59983 +79
============================================
+ Hits 42039 42148 +109
+ Misses 17865 17835 -30
|
madolson
left a comment
There was a problem hiding this comment.
I think this makes sense to me. The slightly more memory usage on some systems is likely OK since I think we still prefer to use jemalloc in most cases.
|
@poiuj overall looks much better now. I would suggest we include some unit tests to cover different types edge cases (for example the case of old style alloc overflow). I am comfortable with the asserts, but we will probably want to trigger ci and daily before we add this. After we finish this PR lets go and fix #453 accordingly |
|
@poiuj the tests looks fine.
Is it really a waste? we already reduced the overflow in the prev implementation and AFAIK we never should have written pass the usable anyhow right? lets say I will allocate 253 sds. Before: I would allocate according to 253+(sizeof(sdshdr8)=3)+1 = 257 --> allocated size of 320 (IIRC) but the usable size is 255 So IMO this is 59 bytes gain:) I still want to verify there are no issues related to backward compatibility (I think RDB does not serialize sds headers, but would like to think on other potential case) |
|
@ranshid your example is correct. It's a 59 bytes gain if we use jemalloc. My top commented is about libc allocator that wouldn't allocate 320 bytes in this case. |
Oh I get it now. yes. indeed this is not too bad IMO. Please also consider avoid the malloc_size use in realloc |
3f6c96f to
a9b378b
Compare
sds type should be determined based on the size of the underlying buffer, not the logical length of the sds. Currently we truncate the alloc field in case buffer is larger than we can handle. It leads to a mismatch between alloc field and the actual size of the buffer. Even considering that alloc doesn't include header size and the null terminator. It also leads to a waste of memory with jemalloc. For example, let's consider creation of sds of length 253. According to the length, the appropriate type is SDS_TYPE_8. But we allocate `253 + sizeof(struct sdshdr8) + 1` bytes, which sums to 257 bytes. In this case jemalloc allocates buffer from the next size bucket. With current configuration on Linux it's 320 bytes. So we end up with 320 bytes buffer, while we can't address more than 255. The same happens with other types and length close enough to the appropriate powers of 2. The downside of the adjustment is that with allocators that do not allocate larger than requested chunks (like GNU allocator), we switch to a larger type "too early". It leads to small waste of memory. Specifically: sds of length 31 takes 35 bytes instead of 33 (2 bytes wasted) sds of length 255 takes 261 bytes instead of 259 (2 bytes wasted) sds of length 65,535 takes 65,545 bytes instead of 65,541 (4 bytes wasted) sds of length 4,294,967,295 takes 4,294,967,313 bytes instead of 4,294,967,305 (8 bytes wasted) Signed-off-by: Vadym Khoptynets <vadymkh@amazon.com>
Make sdsTypeMaxSize account for header and null terminator. Use it in sdsReqType and to assert `usable` is less than max size. Signed-off-by: Vadym Khoptynets <vadymkh@amazon.com>
The test checks that appropriate types are selected for string length. It also checks that sdsAllocSize returns correct allocation size. Signed-off-by: Vadym Khoptynets <vadymkh@amazon.com>
Also eliminate copying of strings - pass NULL as init. Signed-off-by: Vadym Khoptynets <vadymkh@amazon.com>
This is to preserve git history. To be able to use it in sdsReqType a forward declaration is added. Signed-off-by: Vadym Khoptynets <vadymkh@amazon.com>
After the adjustments, jemalloc always returns buffer that fit to chosen SDS type. On the other hand, it's not guaranteed with other allocators. We leave the current behavior for all allocators, but jemalloc. For jemalloc we assert instead. Signed-off-by: Vadym Khoptynets <vadymkh@amazon.com>
With other allocators we can't guarantee alloc field is correct. Signed-off-by: Vadym Khoptynets <vadymkh@amazon.com>
libc allocator can return larger buffer than requested. Unlike jemalloc the buffer sizes are not aligned with SDS sizes. That's why we may need to adjust the SDS type to a larger one to be sure alloc field can hold the size of the allocated buffer. The maximum length for type SDS_TYPE_X is 2^X - header_size(SDS_TYPE_X) - 1. The maxium value to be stored in alloc field is 2^X - 1. When allocated buffer is larger than 2^X + header_size(SDS_TYPE_X), we "move" to a larger type SDS_TYPE_Y. To be sure SDS_TYPE_Y header fits into 2^X + header_size(SDS_TYPE_X) + 1 bytes, the difference between header sizes must be smaller than header_size(SDS_TYPE_X) + 1. We ignore SDS_TYPE_5 as it doesn't have alloc field. Signed-off-by: Vadym Khoptynets <vadymkh@amazon.com>
Signed-off-by: Vadym Khoptynets <vadymkh@amazon.com>
|
Updated the branch. Includes the new approach with adjusting types. Also rebased on the latest unstable. Unfortunately, missed some style changes during conflict resolution. But it's small stuff that I can fix later before the actual merge. |
ranshid
left a comment
There was a problem hiding this comment.
maybe we can make a function to capture the repeated code?:
/* Adjust type if usable won't fit into alloc. */
if (type != SDS_TYPE_5 && usable > sdsTypeMaxSize(type)) {
type = sdsReqType(usable);
hdrlen = sdsHdrSize(type);
usable = bufsize - hdrlen - 1;
assert(usable <= sdsTypeMaxSize(type));
}
Signed-off-by: Vadym Khoptynets <vadymkh@amazon.com>
Signed-off-by: Vadym Khoptynets <vadymkh@amazon.com>
|
LGTM but would like to hear @lipzhu |
Signed-off-by: Vadym Khoptynets <vadymkh@amazon.com>
Signed-off-by: Vadym Khoptynets <vadymkh@amazon.com>
sds type should be determined based on the size of the underlying buffer, not the logical length of the sds. Currently we truncate the alloc field in case buffer is larger than we can handle. It leads to a mismatch between alloc field and the actual size of the buffer. Even considering that alloc doesn't include header size and the null terminator. It also leads to a waste of memory with jemalloc. For example, let's consider creation of sds of length 253. According to the length, the appropriate type is SDS_TYPE_8. But we allocate `253 + sizeof(struct sdshdr8) + 1` bytes, which sums to 257 bytes. In this case jemalloc allocates buffer from the next size bucket. With current configuration on Linux it's 320 bytes. So we end up with 320 bytes buffer, while we can't address more than 255. The same happens with other types and length close enough to the appropriate powers of 2. The downside of the adjustment is that with allocators that do not allocate larger than requested chunks (like GNU allocator), we switch to a larger type "too early". It leads to small waste of memory. Specifically: sds of length 31 takes 35 bytes instead of 33 (2 bytes wasted) sds of length 255 takes 261 bytes instead of 259 (2 bytes wasted) sds of length 65,535 takes 65,545 bytes instead of 65,541 (4 bytes wasted) sds of length 4,294,967,295 takes 4,294,967,313 bytes instead of 4,294,967,305 (8 bytes wasted) --------- Signed-off-by: Vadym Khoptynets <vadymkh@amazon.com>
sds type should be determined based on the size of the underlying buffer, not the logical length of the sds. Currently we truncate the alloc field in case buffer is larger than we can handle. It leads to a mismatch between alloc field and the actual size of the buffer. Even considering that alloc doesn't include header size and the null terminator.
It also leads to a waste of memory with jemalloc. For example, let's consider creation of sds of length 253. According to the length, the appropriate type is SDS_TYPE_8. But we allocate
253 + sizeof(struct sdshdr8) + 1bytes, which sums to 257 bytes. In this case jemalloc allocates buffer from the next size bucket. With current configuration on Linux it's 320 bytes. So we end up with 320 bytes buffer, while we can't address more than 255.The same happens with other types and length close enough to the appropriate powers of 2.
The downside of the adjustment is that with allocators that do not allocate larger than requested chunks (like GNU allocator), we switch to a larger type "too early". It leads to small waste of memory. Specifically: sds of length 31 takes 35 bytes instead of 33 (2 bytes wasted) sds of length 255 takes 261 bytes instead of 259 (2 bytes wasted) sds of length 65,535 takes 65,545 bytes instead of 65,541 (4 bytes wasted) sds of length 4,294,967,295 takes 4,294,967,313 bytes instead of 4,294,967,305 (8 bytes wasted)