[poppler] [PATCH] ~10% speedup for loading/parsing a PDF file through simple GooString optimization

[Krzysztof Kowalczyk]

Hello,

Recently I've been profiling poppler, seeking ways to speed it up. I
believe I found a simple way to speedup loading/parsing of a PDF file
by ~10% via very simple optimization to GooString.

poppler allocates and frees a lot of objects, especially GooString objects. In
my profiling malloc() and free() are at the top of functions that take most of
the time.

I instrumented the code to record sizes of GooStrings at the time of
destruction. It turns out that ~90% of them are 16 bytes or less.

Currently allocating GooString() requires 2 malloc()s:
* one from new to allocate the object itself
* another one to allocate s pointer to a string

A very simple optimization is to keep a small buffer within GooString itself and
only allocate new space if the string gets bigger. This halfs the number of
malloc() calls for string that entirely fit in the buffer. In case of poppler, a
buffer of size 16 would eliminate 45% malloc()/free() calls that are caused by
GooString().

Another good part is that it doesn't even use more memory. malloc() rounds
allocation sizes anyway (by 16 bytes on Ubuntu, try printf("allocation rounding:
%d\n", -(int)((char*)malloc(1) - (char*)malloc(1)));) and the OS needs
book-keeping information (BOOK_KEEP_SIZE) which is implementation dependent but
usually not less than 8 bytes. Assuming those parameters, memory used by current
implementation of GooString is:
* BOOK_KEEP_SIZE + round_16(sizeof(GooString)) + round_16($str_size) +
BOOK_KEEP_SIZE = 2*BOOK_KEEP_SIZE + round_16(8) + round_16($str_size) =
2*8+16+round_16($str_size) = 32+round_16($str_size)
In implementation with static buffer, assuming buffer size 16:
* for $str_size <= 16: BOOK_KEEP_SIZE + round_16(sizeof(GooString) +
round_16($str_size) = 8 + round_16(24) = 8 + 32 = 40 so it's actually less real
memory used
For $str_size > 16 a bit more is used.

How to choose size of static space: currently I use 16 but it might be better to
use 24 (so that sizeof(GooString) is 32 because it'll probably be anyway due to
rounding to 16 bytes).

Does it give any real speedup? My test consisted of just loading and
parsing (no rendering)
of PDFReference16.pdf file (PDF 1.6 spec available from Adobe website) which is
about 8.72 M in size.

I used a release build and recorded user time averaged over 4 runs. I got a 10%
speedup (from 1453.095 milliseconds to 1303.7425 milliseconds).
(disclaimer: as with any benchmark, results will probably vary
depending on what file is being profiled).

On top of that, the implementation is dead simple.

Attached patch has a #define FAST_GOO_STRING in GooString.h so that interested
parties can easily compile both versions and compare the speeds.

It also has #define DO_HIST that adds code to collect string sizes at the time
of deletion. This shows that majority of strings in poppler is <=16 bytes.

Howerver, I do not recommend keeping those #defines in final version. It's
trivial to remove them.

This could probably be also applied to UGooString.

In general, it seems that a good strategy for improving poppler
performance would be to decrease the number of malloc()/free() calls
e.g. by stack-allocation of objects as opposed to constantly
new/delete them. Even after this optimization malloc()/free() are at
the top of profile.

This is bug: https://bugs.freedesktop.org/show_bug.cgi?id=7808

-- kjk | http://blog.kowalczyk.info
-------------- next part --------------
Index: GooString.cc
===================================================================
--- GooString.cc	(revision 36)
+++ GooString.cc	(working copy)
@@ -21,7 +21,56 @@
 #include "gtypes.h"
 #include "GooString.h"
 
-static inline int size(int len) {
+#define HIST_SIZE 12048
+
+#define SIZE 0
+#define COUNT 1
+static int gStrSizeHist[HIST_SIZE][2] = {0};
+static int gHistEntries = 0;
+
+extern "C" {
+#ifdef _WIN32
+  void win32_dbg_out(const char *format, ...);
+  #define DBG_OUT win32_dbg_out
+  #else
+  #define DBG_OUT printf
+#endif
+}
+
+/* slow but works */
+static void histAdd(int size)
+{
+#ifdef DO_HIST
+    int     i;
+
+    for (i = 0; i < gHistEntries; i++) {
+        if (gStrSizeHist[i][SIZE] == size) {
+            gStrSizeHist[i][COUNT] += 1;
+            return;
+        }
+    }
+    if (gHistEntries >= (HIST_SIZE - 1)) {
+        DBG_OUT("gHistEntries (%d) reached max HIST_SIZE (%d)\n", gHistEntries, (int)HIST_SIZE);
+        return;
+    }
+    gStrSizeHist[i][SIZE] = size;
+    gStrSizeHist[i][COUNT] = 1;
+    ++gHistEntries;
+#endif
+}
+
+void histDump(void)
+{
+#ifdef DO_HIST
+    DBG_OUT("STRING HISTOGRAM DUMP START\n");
+    for (int i = 0; i < gHistEntries; i++) {
+        DBG_OUT("%d,%d\n", gStrSizeHist[i][SIZE], gStrSizeHist[i][COUNT]);
+    }
+    DBG_OUT("STRING HISTOGRAM DUMP END\n");
+#endif
+}
+
+static inline int rounded_size(int len) {
   int delta;
 
   delta = len < 256 ? 7 : 255;
@@ -32,16 +81,35 @@
   char *s1;
 
   if (!s) {
-    s = new char[size(length1)];
-  } else if (size(length1) != size(length)) {
-    s1 = new char[size(length1)];
+#ifdef FAST_GOO_STRING
+    if (rounded_size(length1) <= GSTR_STATIC_SIZE)
+        s = sStatic;
+    else
+        s = new char[rounded_size(length1)];
+#else
+    s = new char[rounded_size(length1)];
+#endif
+  } else if (rounded_size(length1) != rounded_size(length)) {
+#ifdef FAST_GOO_STRING
+    if (rounded_size(length1) <= GSTR_STATIC_SIZE)
+        s1 = sStatic;
+    else
+        s1 = new char[rounded_size(length1)];
+#else
+      s1 = new char[rounded_size(length1)];
+#endif
     if (length1 < length) {
       memcpy(s1, s, length1);
       s1[length1] = '\0';
     } else {
       memcpy(s1, s, length + 1);
     }
+#ifdef FAST_GOO_STRING
+    if (s != sStatic)
+        delete[] s;
+#else
     delete[] s;
+#endif
     s = s1;
   }
 }
@@ -117,7 +185,9 @@
 }
 
 GooString::~GooString() {
-  delete[] s;
+  histAdd(rounded_size(length));
+  if (s != sStatic)
+    delete[] s;
 }
 
 GooString *GooString::clear() {
Index: GooString.h
===================================================================
--- GooString.h	(revision 36)
+++ GooString.h	(working copy)
@@ -17,6 +17,14 @@
 
 #include "gtypes.h"
 
+#define FAST_GOO_STRING 1
+//#define DO_HIST 1
+void histDump(void);
+
+/* I think this could just as well be 24 so that sizeof(GooString) is 32,
+   because it'll probably be anyway. */
+#define GSTR_STATIC_SIZE 16
+
 class GooString {
 public:
 
@@ -90,6 +98,9 @@
 
 private:
 
+#ifdef FAST_GOO_STRING
+  char sStatic[GSTR_STATIC_SIZE];
+#endif
   int length;
   char *s;