[HTCondor-devel] Examining in-memory representation of ClassAds

[Brian Bockelman <bbockelm@xxxxxxxxxxx>]

Hi,

The size of ClassAds in memory has been bothering me lately.  Being that a current scaling bottleneck is submitter memory usage and that schedd size is about 1/3 of the problem, this is an important thing to think about.

I decided to prod at it a bit over the long weekend.

Running the "without_cache" example on my Mac (LLVM / libc++ toolchain) over the test corpus of data (testdata.txt in git) caused memory usage of 160MB for 22MB of text data input.  That means about a factor-8 increase from text to in-memory.  With classad compression on, memory usage decreased to ~130MB - a decrease, sure, but at a fairly high cost.

Looking under the hood, there's a lot of nasties sitting around:
- Each ClassAdExprEnvelope object (the sub-class of ExprTree which represents a value in the cache) takes a minimum of 40 bytes -- this is just the placeholder, not the size of the object in cache itself.  So, literal expressions - such as "true" take >40 bytes to represent!
- The underlying data structure of a classad is a hash map.  While an efficient data structure for lookup, it is inefficient in memory - by construction, it keeps a few empty buckets and is pointer-heavy.
  - The keys in this map are strings; at a minimum, this is 16 bytes per attribute.
  - The average size of the hash map is relatively small - <200 elements.  In CMS, we've found that a sorted vector is comparable in lookup speed and much more efficient in memory.  The solution I outline below will keep most ClassAds on a page or two in memory.
- The classad cache is a hash map of hash maps, a very memory-inefficient data structure.

Doing the math, each classad averaged to be 19KB of memory - 109 bytes on average per attribute!  That's HUGE.

Not being one to sit still, I sat down to a redesign of the internals.

First, I added a binary packed representation of each expression.  This drew heavily from the DER representation of ASN.1.  For example, the literal "1" is going to be represented as:

0x41 0x01 0x01
- Byte 1 is the header, determining the type (0x40 is the code I use for ValueType = INTEGER_VALUE and 0x01 is the code for a literal).
- Byte 2 is the number of bytes in the integer encoding.
- Byte 3 is the integer encoding itself.

Most literals can be represented in under 10 bytes; attributes and such are often under 21 (an important cutoff later).

Next, I switched the underlying data structure in the classad to a sorted vector.  I created an in-memory lookup table of "short" -> "string" for the attribute name.  The objects in the vector are of the form:

ClassAdNVP
  * short index (2 bytes).  This is the index of the attribute string in the lookup array.
  * char flags (1 byte).  True if we use an embedded packing of the value; false if `value` is a valid pointer.
  * char m_data[5] (5 bytes).  If flags, then this is the packing of the value; otherwise, padding.
   * union {
         * char m_rest[8] (16 bytes). If flags, then this is the remainder of the value
         * shared_ptr<CacheKey> value (16 bytes). Pointer to an CacheKey object representing this value.
            - Note: for a complete implementation, we may want to switch this back to a "ExprTree *" especially if we want to keep the "ExprTree *"-heavy APIs into ClassAds.
      } _m

If the packed representation of the value is less than 21 bytes, we do not use the cache and simply embed the value in the ClassAdNVP itself.

The CacheKey is an entry in the ClassAd cache map (which contains CacheKey* keys and weak_ptr<CacheKey> values).  The CacheKey basically just a string right now - although it could have members be added back to short-circuit ClassAd expression parsing like it does now.  

The APIs have to be changed to return shared_ptr<ExprTree> instead of "ExprTree *" because the ClassAd no longer maintains an internal ExprTree object.  This touches many interfaces - *but* cleans up ownership issues, which have always been horrible in libclassad.

The upshot is that expressions which can be packed in less than 21 bytes are embedded in the classad itself; larger expressions are kept in the cache, which has significantly smaller overhead by reducing the number of pointers in the data structure.

SUMMARY:

With the in-memory format changes described above, memory usage for the 22MB sample corpus is 29MB.  While the savings aren't as significant as I had hoped (wouldn't it be nice to have the text format be larger than the parsed form?), it's a 77% savings over current with compression and 82% savings over current without compression.

I think this shows the approach I took is viable, but will require more engineering than a holiday weekend to bring to fruition.  A lot of the API methods were left as stubs in order to concentrate solely on memory layout.  However, I hope this shows there's a significantly better approach compared to current methods.

Brian

Attachment: smime.p7s
Description: S/MIME cryptographic signature