Hello, I did notice today that GooString uses the small string optimization but uses a hard-coded size for the static buffer, so that the final object size depends on the architecture on which Poppler is built.
For example, in contrast to the source code comment, on my amd64 machine, sizeof(GooString) is actually 40 instead of the desired 32, which could mean that we are wasting (48 - 40) / 48 = 16.7 % of the memory allocated for small strings. The first part of the attached patch adds a private helper class GooString::MemoryLayout to simulate the memory layout of GooString that the compiler will generate and uses this to compute the static buffer size based on the desired final object size. However, if this is done using 32 bytes the small buffer is shortened from 24 to 16 bytes on LP64 systems. Hence the second part of the patch puts the static buffer and the pointer to a dynamic buffer into a union to save space which means that small strings will have 24/40 bytes within 32/48-byte GooString objects. Deciding whether a GooString is allocated statically or dynamically is done using the sign of the length field, i.e. effectively using of one its bits as a flag. The changes this implies throughout the GooString class can mostly be encapsulated using some inline helper methods, but the code will become more branch-heavy due to the necessary checks and decisions. I am still working on measuring the effects this has on the runtime but would already like to ask for comments whether the increased complexity of the second part of the patch seems sensible. I think the first part of the patch should be included in some form (maybe using a different technique than the helper class) if the behaviour of malloc implied by the comment is still valid. Some simple measurements using cold runs of a release build of the stress-poppler-dir program from the Qt tests with a directory of some mathematical documents and the call to Page::renderToImage replaced by calls to Page::textList and Page::search yields the following: [layout variant (static buffer size/final object size)] current (24/40): 278 s adjusted (16/32): 277 s adjusted (24/48): 274 s compact (24/32): 272 s compact (40/48): 274 s I would preliminarily interpret this as no significant change in runtime and would therefore argue that the memory usage improvements should be implemented, probably using the compact 24/32 layout after further tests and benchmarks. I will try runnning the complete regression test suite to make sure there are none, since this does seem like a high-risk change. Maybe this also yields some more definite performance numbers. I would greatly appreciate any advice on how to benchmark this most effectively. Best regards, Adam.
From 6538224cb0bbf8110b7d8ed1d7003a9a006319e2 Mon Sep 17 00:00:00 2001 From: Adam Reichold <[email protected]> Date: Mon, 29 Jun 2015 10:57:20 +0200 Subject: [PATCH 1/2] Adjust memory layout computation of GooString GooString uses the small string optimization but the static buffer size is hard-coded and hence the final object size becomes dependent on architecture. This adds a helper class to compute the memory layout at compile time so that the target object size of e.g. 32 or another multiple of 16 is achieved. This also adds an overload so that the C string returned by GooString's getCString method respect the constness of this and fixes a constness issue in the lexer tests. --- goo/GooString.h | 16 +++++++++++----- qt4/tests/check_lexer.cpp | 2 +- qt5/tests/check_lexer.cpp | 2 +- 3 files changed, 13 insertions(+), 7 deletions(-) diff --git a/goo/GooString.h b/goo/GooString.h index c6fb100..b9e45f3 100644 --- a/goo/GooString.h +++ b/goo/GooString.h @@ -114,13 +114,14 @@ public: ~GooString(); // Get length. - int getLength() { return length; } + int getLength() const { return length; } // Get C string. - char *getCString() const { return s; } + char *getCString() { return s; } + const char *getCString() const { return s; } // Get <i>th character. - char getChar(int i) { return s[i]; } + char getChar(int i) const { return s[i]; } // Change <i>th character. void setChar(int i, char c) { s[i] = c; } @@ -173,8 +174,13 @@ private: // you can tweak this number for a different speed/memory usage tradeoffs. // In libc malloc() rounding is 16 so it's best to choose a value that // results in sizeof(GooString) be a multiple of 16. - // 24 makes sizeof(GooString) to be 32. - static const int STR_STATIC_SIZE = 24; + class MemoryLayout { + char c[sizeof(char*)]; + int i; + char* s; + }; + + static const int STR_STATIC_SIZE = 32 - sizeof(MemoryLayout) + sizeof(char*); int roundedSize(int len); diff --git a/qt4/tests/check_lexer.cpp b/qt4/tests/check_lexer.cpp index ea834c8..243a592 100644 --- a/qt4/tests/check_lexer.cpp +++ b/qt4/tests/check_lexer.cpp @@ -12,7 +12,7 @@ private slots: void TestLexer::testNumbers() { - char *data = "0 1 -1 2147483647 -2147483647 2147483648 -2147483648 4294967297 -2147483649 0.1 1.1 -1.1 2147483647.1 -2147483647.1 2147483648.1 -2147483648.1 4294967297.1 -2147483649.1 9223372036854775807 18446744073709551615"; + char data[] = "0 1 -1 2147483647 -2147483647 2147483648 -2147483648 4294967297 -2147483649 0.1 1.1 -1.1 2147483647.1 -2147483647.1 2147483648.1 -2147483648.1 4294967297.1 -2147483649.1 9223372036854775807 18446744073709551615"; Object dummy; MemStream *stream = new MemStream(data, 0, strlen(data), &dummy); Lexer *lexer = new Lexer(NULL, stream); diff --git a/qt5/tests/check_lexer.cpp b/qt5/tests/check_lexer.cpp index ea834c8..243a592 100644 --- a/qt5/tests/check_lexer.cpp +++ b/qt5/tests/check_lexer.cpp @@ -12,7 +12,7 @@ private slots: void TestLexer::testNumbers() { - char *data = "0 1 -1 2147483647 -2147483647 2147483648 -2147483648 4294967297 -2147483649 0.1 1.1 -1.1 2147483647.1 -2147483647.1 2147483648.1 -2147483648.1 4294967297.1 -2147483649.1 9223372036854775807 18446744073709551615"; + char data[] = "0 1 -1 2147483647 -2147483647 2147483648 -2147483648 4294967297 -2147483649 0.1 1.1 -1.1 2147483647.1 -2147483647.1 2147483648.1 -2147483648.1 4294967297.1 -2147483649.1 9223372036854775807 18446744073709551615"; Object dummy; MemStream *stream = new MemStream(data, 0, strlen(data), &dummy); Lexer *lexer = new Lexer(NULL, stream); -- 2.4.4 From 41765e2f6fa51ab2bc1bd26ef09cbcd5ccc4bc92 Mon Sep 17 00:00:00 2001 From: Adam Reichold <[email protected]> Date: Mon, 29 Jun 2015 13:17:58 +0200 Subject: [PATCH 2/2] Decrease memory usage of GooString using union The small string optimization within GooString currently keeps both the static buffer and a pointer to it or a dynamic buffer valid even though only one will be used at any given point in time. This change puts both variables within a discriminated union whose actual type is determined by the sign of the length member which does for example save 8 bytes per object on a 64 bit architecture. --- goo/GooString.cc | 249 +++++++++++++++++++++++++++++++++---------------------- goo/GooString.h | 43 +++++++--- 2 files changed, 180 insertions(+), 112 deletions(-) diff --git a/goo/GooString.cc b/goo/GooString.cc index 3f22f36..4c3fed4 100644 --- a/goo/GooString.cc +++ b/goo/GooString.cc @@ -43,6 +43,9 @@ #include <ctype.h> #include <assert.h> #include <math.h> + +#include <algorithm> + #include "gmem.h" #include "GooString.h" @@ -140,46 +143,61 @@ int inline GooString::roundedSize(int len) { // Make sure that the buffer is big enough to contain <newLength> characters // plus terminating 0. -// We assume that if this is being called from the constructor, <s> was set -// to NULL and <length> was set to 0 to indicate unused string before calling us. void inline GooString::resize(int newLength) { - char *s1 = s; + char *p = s(); - if (!s || (roundedSize(length) != roundedSize(newLength))) { - // requires re-allocating data for string - if (newLength < STR_STATIC_SIZE) { - s1 = sStatic; - } else { - // allocate a rounded amount - if (s == sStatic) - s1 = (char*)gmalloc(roundedSize(newLength)); - else - s1 = (char*)grealloc(s, roundedSize(newLength)); - } - if (s == sStatic || s1 == sStatic) { - // copy the minimum, we only need to if are moving to or - // from sStatic. - // assert(s != s1) the roundedSize condition ensures this - if (newLength < length) { - memcpy(s1, s, newLength); + // Will the new string be static? + if (newLength < STR_STATIC_SIZE) { + + // Is the current string dynamic? + if (isDynamic()) { + + // We will only copy only the minimum number of characters + // and use that signedLength is positive. + memcpy(sStatic, p, std::min(newLength, signedLength)); + + // Free the obsolete dynamic buffer + gfree(p); + } + + p = sStatic; + signedLength = -newLength; + + // Will the new string be dynamic? + } else { + + // Is the current string static? + if (isStatic()) { + + // Allocate a rounded number of characters + p = (char*)gmalloc(roundedSize(newLength)); + + // We will only copy only the minimum number of characters + // and use that signedLength is non-positive. + memcpy(p, sStatic, std::min(newLength, -signedLength)); + + // Is the current string dynamic? } else { - memcpy(s1, s, length); + + // Do we need to reallocate? + if (roundedSize(length()) != roundedSize(newLength)) { + + // Reallocate a rounded number of characters + p = (char*)grealloc(p, roundedSize(newLength)); + } } - if (s != sStatic) - gfree(s); - } + sDynamic = p; + signedLength = newLength; } - s = s1; - length = newLength; - s[length] = '\0'; + // Make sure to zero terminate no matter which type of storage we are using. + p[length()] = '\0'; } GooString* GooString::Set(const char *s1, int s1Len, const char *s2, int s2Len) { int newLen = 0; - char *p; if (s1) { if (CALC_STRING_LEN == s1Len) { @@ -198,53 +216,61 @@ GooString* GooString::Set(const char *s1, int s1Len, const char *s2, int s2Len) } resize(newLen); - p = s; + + char *p = s(); + if (s1) { memcpy(p, s1, s1Len); p += s1Len; } + if (s2) { memcpy(p, s2, s2Len); p += s2Len; } + return this; } GooString::GooString() { - s = NULL; - length = 0; - Set(NULL); + signedLength = 0; + sStatic[0] = '\0'; } GooString::GooString(const char *sA) { - s = NULL; - length = 0; + signedLength = 0; + sStatic[0] = '\0'; + Set(sA, CALC_STRING_LEN); } GooString::GooString(const char *sA, int lengthA) { - s = NULL; - length = 0; + signedLength = 0; + sStatic[0] = '\0'; + Set(sA, lengthA); } -GooString::GooString(GooString *str, int idx, int lengthA) { - s = NULL; - length = 0; - assert(idx + lengthA <= str->length); +GooString::GooString(const GooString *str, int idx, int lengthA) { + signedLength = 0; + sStatic[0] = '\0'; + + assert(idx + lengthA <= str->length()); Set(str->getCString() + idx, lengthA); } GooString::GooString(const GooString *str) { - s = NULL; - length = 0; - Set(str->getCString(), str->length); + signedLength = 0; + sStatic[0] = '\0'; + + Set(str->getCString(), str->length()); } -GooString::GooString(GooString *str1, GooString *str2) { - s = NULL; - length = 0; - Set(str1->getCString(), str1->length, str2->getCString(), str2->length); +GooString::GooString(const GooString *str1, const GooString *str2) { + signedLength = 0; + sStatic[0] = '\0'; + + Set(str1->getCString(), str1->length(), str2->getCString(), str2->length()); } GooString *GooString::fromInt(int x) { @@ -275,8 +301,8 @@ GooString *GooString::formatv(const char *fmt, va_list argList) { } GooString::~GooString() { - if (s != sStatic) - gfree(s); + if (isDynamic()) + gfree(sDynamic); } GooString *GooString::clear() { @@ -293,11 +319,16 @@ GooString *GooString::append(GooString *str) { } GooString *GooString::append(const char *str, int lengthA) { - int prevLen = length; + const int prevLen = length(); + if (CALC_STRING_LEN == lengthA) lengthA = strlen(str); - resize(length + lengthA); - memcpy(s + prevLen, str, lengthA); + + resize(prevLen + lengthA); + + char *p = s(); + memcpy(p + prevLen, str, lengthA); + return this; } @@ -788,59 +819,70 @@ GooString *GooString::insert(int i, GooString *str) { } GooString *GooString::insert(int i, const char *str, int lengthA) { - int prevLen = length; + const int prevLen = length(); + if (CALC_STRING_LEN == lengthA) lengthA = strlen(str); - resize(length + lengthA); - memmove(s+i+lengthA, s+i, prevLen-i); - memcpy(s+i, str, lengthA); + resize(prevLen + lengthA); + + char *p = s(); + memmove(p+i+lengthA, p+i, prevLen-i); + memcpy(p+i, str, lengthA); + return this; } GooString *GooString::del(int i, int n) { - int j; - if (i >= 0 && n > 0 && i + n > 0) { - if (i + n > length) { - n = length - i; + char *p = s(); + const int prevLen = length(); + + if (i + n > prevLen) { + n = prevLen - i; } - for (j = i; j <= length - n; ++j) { - s[j] = s[j + n]; + + for (int j = i; j <= prevLen - n; ++j) { + p[j] = p[j + n]; } - resize(length - n); + + resize(prevLen - n); } + return this; } GooString *GooString::upperCase() { - int i; + char *p = s(); + const int n = length(); - for (i = 0; i < length; ++i) { - if (islower(s[i])) - s[i] = toupper(s[i]); + for (int i = 0; i < n; ++i) { + if (islower(p[i])) + p[i] = toupper(p[i]); } return this; } GooString *GooString::lowerCase() { - int i; + char *p = s(); + const int n = length(); - for (i = 0; i < length; ++i) { - if (isupper(s[i])) - s[i] = tolower(s[i]); + for (int i = 0; i < n; ++i) { + if (isupper(p[i])) + p[i] = tolower(p[i]); } return this; } int GooString::cmp(GooString *str) const { - int n1, n2, i, x; - char *p1, *p2; + const char *p1 = s(); + const int n1 = length(); - n1 = length; - n2 = str->length; - for (i = 0, p1 = s, p2 = str->s; i < n1 && i < n2; ++i, ++p1, ++p2) { - x = *p1 - *p2; + const char *p2 = str->s(); + const int n2 = str->length(); + + for (int i = 0; i < n1 && i < n2; ++i, ++p1, ++p2) { + const int x = *p1 - *p2; if (x != 0) { return x; } @@ -849,15 +891,15 @@ int GooString::cmp(GooString *str) const { } int GooString::cmpN(GooString *str, int n) const { - int n1, n2, i, x; - char *p1, *p2; - - n1 = length; - n2 = str->length; - for (i = 0, p1 = s, p2 = str->s; - i < n1 && i < n2 && i < n; - ++i, ++p1, ++p2) { - x = *p1 - *p2; + const char *p1 = s(); + const int n1 = length(); + + const char *p2 = str->s(); + const int n2 = str->length(); + + int i; + for (i = 0; i < n1 && i < n2 && i < n; ++i, ++p1, ++p2) { + const int x = *p1 - *p2; if (x != 0) { return x; } @@ -869,12 +911,14 @@ int GooString::cmpN(GooString *str, int n) const { } int GooString::cmp(const char *sA) const { - int n1, i, x; - const char *p1, *p2; + const char *p1 = s(); + const int n1 = length(); + + const char *p2 = sA; - n1 = length; - for (i = 0, p1 = s, p2 = sA; i < n1 && *p2; ++i, ++p1, ++p2) { - x = *p1 - *p2; + int i; + for (i = 0; i < n1 && *p2; ++i, ++p1, ++p2) { + const int x = *p1 - *p2; if (x != 0) { return x; } @@ -889,12 +933,14 @@ int GooString::cmp(const char *sA) const { } int GooString::cmpN(const char *sA, int n) const { - int n1, i, x; - const char *p1, *p2; + const char *p1 = s(); + const int n1 = length(); - n1 = length; - for (i = 0, p1 = s, p2 = sA; i < n1 && *p2 && i < n; ++i, ++p1, ++p2) { - x = *p1 - *p2; + const char *p2 = sA; + + int i; + for (i = 0; i < n1 && *p2 && i < n; ++i, ++p1, ++p2) { + const int x = *p1 - *p2; if (x != 0) { return x; } @@ -912,17 +958,20 @@ int GooString::cmpN(const char *sA, int n) const { } GBool GooString::endsWith(const char *suffix) const { - int suffixLen = strlen(suffix); + const int len = length(); + const int suffixLen = strlen(suffix); - if (length < suffixLen) + if (len < suffixLen) return gFalse; - return strcmp(s + length - suffixLen, suffix) == 0; + return strcmp(s() + len - suffixLen, suffix) == 0; } GBool GooString::hasUnicodeMarker(void) { - return length > 1 && (s[0] & 0xff) == 0xfe && (s[1] & 0xff) == 0xff; + const char *p = s(); + + return length() > 1 && (p[0] & 0xff) == 0xfe && (p[1] & 0xff) == 0xff; } GooString *GooString::sanitizedName(GBool psmode) diff --git a/goo/GooString.h b/goo/GooString.h index b9e45f3..49caa32 100644 --- a/goo/GooString.h +++ b/goo/GooString.h @@ -62,7 +62,7 @@ public: GooString(const char *sA, int lengthA); // Create a string from <lengthA> chars at <idx> in <str>. - GooString(GooString *str, int idx, int lengthA); + GooString(const GooString *str, int idx, int lengthA); // Set content of a string to concatination of <s1> and <s2>. They can both // be NULL. if <s1Len> or <s2Len> is CALC_STRING_LEN, then length of the string @@ -75,7 +75,7 @@ public: GooString *copy() const { return new GooString(this); } // Concatenate two strings. - GooString(GooString *str1, GooString *str2); + GooString(const GooString *str1, const GooString *str2); // Convert an integer to a string. static GooString *fromInt(int x); @@ -114,17 +114,17 @@ public: ~GooString(); // Get length. - int getLength() const { return length; } + int getLength() const { return length(); } // Get C string. - char *getCString() { return s; } - const char *getCString() const { return s; } + char *getCString() { return s(); } + const char *getCString() const { return s(); } // Get <i>th character. - char getChar(int i) const { return s[i]; } + char getChar(int i) const { return s()[i]; } // Change <i>th character. - void setChar(int i, char c) { s[i] = c; } + void setChar(int i, char c) { s()[i] = c; } // Clear string to zero length. GooString *clear(); @@ -175,20 +175,39 @@ private: // In libc malloc() rounding is 16 so it's best to choose a value that // results in sizeof(GooString) be a multiple of 16. class MemoryLayout { - char c[sizeof(char*)]; int i; - char* s; + union { + char c[sizeof(char*)]; + char* s; + }; }; static const int STR_STATIC_SIZE = 32 - sizeof(MemoryLayout) + sizeof(char*); int roundedSize(int len); - char sStatic[STR_STATIC_SIZE]; - int length; - char *s; + // Uses the small string optimization with the static buffer + // and the pointer to a dynamic buffer sharing a union. + // If the signedLength is non-positive, the string is using + // the static buffer. Otherwise is uses the dynamic buffer. + // Therefore the empty string is a zero-length small string. + int signedLength; + + union { + char sStatic[STR_STATIC_SIZE]; + char *sDynamic; + }; + + bool isStatic() const { return signedLength <= 0; } + bool isDynamic() const { return signedLength > 0; } + + int length() const { return signedLength < 0 ? -signedLength : signedLength; } + + char* s() { return signedLength <= 0 ? sStatic : sDynamic; } + const char* s() const { return signedLength <= 0 ? sStatic : sDynamic; } void resize(int newLength); + #ifdef LLONG_MAX static void formatInt(long long x, char *buf, int bufSize, GBool zeroFill, int width, int base, -- 2.4.4
signature.asc
Description: OpenPGP digital signature
_______________________________________________ poppler mailing list [email protected] http://lists.freedesktop.org/mailman/listinfo/poppler
