Science of programming Wed, 23 Aug 2017 12:03:42 +0300 Wed, 23 Aug 2017 12:03:42 +0300 Jekyll v3.4.3 JSM as Machine Learning <p>For a long time I wanted to establish a layman’s description of JSM method, its application in machine learning and showcase a practical example of its use. Instead of focusing on the intricate theoretical foundation it will be based off the simplified definition obtained by <a href="" title="Set Theoretic Definition of JSM">Anshakov</a>. The paper is sadly in Russian as is the case with most information on JSM, hence today’s post.</p> <h2 id="foundations">Foundations</h2> <p>Let’s assume we have N objects, each described by M binary attributes and a singular property which is one of “negative”, “positive” or “tau” denoting the absence or the presence of property and tau being yet to be determined value. This set of objects is called the Context. Observe that we can map an arbitrary set of objects to a set of attributes common to all of them. Getting attributes that are common to a number of objects is an intersection of objects. Likewise we can pick an arbitrary set of attributes and find all objects that have these attributes. <img src="" alt="An example context" title="An example context" /> When things get more interesting is when we combine both operations going e.g. attributes -&gt; objects -&gt; attributes or objects -&gt; attributes -&gt; objects. Observe that for instance we may start with a single attribute but once we intersect all objects having it we may obtain more attributes common to all of them. This operation (application of both tr ansitions) is called closing the set of attributes or objects. On the figure above closing the 1st attribute gives us a set of 1st and 3rd attribute. Let me point out without proof that once a set is obtained by closure continuous application of closing operator is idempotent. The set is called closed set. Also a closed set can be described in any of two ways - a set of objects or corresponding set of attributes. Such a pair of equivalent sets of objects and attributes is called a concept. The concept is a crucial notion, as it represents what JSM calls a hypothesis provided however that all of objects have the same property. In this case it is understood that attributes are the cause of the property (or the absence of it) and objects are examples that support this hypothesis. Obtaining these hypotheses represent a typical empiric reasoning - induction. It is therefore prudent to mine all hypotheses from the context and latter apply the best of them for classification. The “best of them” is the important bit that I will touch on later.</p> <h2 id="basic-jsm">Basic JSM</h2> <p>First let’s focus on the mining all concepts problem. Straightforward solution is to intersect pairs of objects, then close the results, following that add a new object to each set and repeat. The problem is checking already obtained sets would require a large lookup table of sorts. An intriguing algorithm due to <a href=" a/2013/02/20/1306839179/Comparing%20performance%20of%20algorithms%20for%20generating%20concept.pdf" title="Comparing algorithms">Kuznetcov</a> is able to detect if the set was already obtained based on canonicalization rule without any lookups. Careful reader will observe that linked paper defines similar problem calling it formal concept analysis. Indeed the two branches of science are closely related, and easily borrow algorithms from one another. Not going to describe the Close by One algorithm as its author outlines it better. Still consider that it essentially starts as our naive version but with attributes, adding them one by one and performing a closure after each addition. Importantly it discards a concept if after closure it gets any new attribute preceding the current one and not in the parent set.</p> <p>This is what makes close by one produce each unique concept (hypothesis) only once. Performing close by one on a set of all positive examples gives us positive hypotheses and likewise we can separately obtain all negative hypotheses. Then JSM procedure canceles out equal hypotheses of opposite sets and all hypotheses that fully intersect with some example of the opposite sign. Hypotheses thus obtained could be used as rules for classification. I would also point out without going into details that there are different strategies for filtering hypotheses beyond this one.</p> <p>Classification of tau examples is done by intersecting with hypotheses, each full intersection (if an intersection is equal to hypothesis) is considered as a vote in favor of (not) having a property. Here is where some tuning comes in - for a classic version only unanimous vote is considered as definitive. Non-classic JSM may choose to go with different majority proportions. Inconclusive votes leave example in a contradictory state, which is in contrast with most machine learning techniques that would give only 1 or 0 regardless. Moreover the whole set of posible answers is 4-fold: unknown (no covered by any hypothesis), positive, negative and contradiction. A lot of contradictions or unknowns means that one needs to work on the quality of training data and/or selection of attributes, also to consider non-classic JSM.</p> <h2 id="generalizing">Generalizing</h2> <p>Up to this point the problem space was fairly limited - only binary attributes and a single binary property. First an obvious extension is considering P independent properties at once. One can go about it by performing 2P separate inductions - each property times plus and minus. More interestingly it can be done in exactly one induction by encoding properties as a pair of attributes - one for minus and one for plus. Then a single pass of induction is performed discarding concepts whose parents properties have zero in intersection. Going to tau examples (which can be partially tau) during classification they count as two ones to allow simpler processing.</p> <p>Getting more ambitious and speaking of non-binary attributes, a typical enumeration can be encoded as binary number. For continuous intervals there are more clever encodings. I will cover one particular encoding - “activity level”, which is a number in (0, 1.0) range where having large value implies greater activity. The key observation is that activity of 0.5 implies having more then 0.25, therefore an intersection of activities is the minimum of the two. Finally the binary encoding is done by separating the range in a fixed number of steps and denoting a binary attribute for each step. With such an arrangement binary intersection will magically obtain the required logical result. This trick works both for properties and attributes. Other clever encodings are a topic for a separate article. <img src="" alt="Level encoding" title="Level encoding" /></p> <h2 id="case-study---mushrooms">Case study - Mushrooms</h2> <p>In this chapter I’m finally getting to something working in the real life, showcasing my Scala <a href="" title="JSM4S">library for JSM</a>. I also have a faster but more cumbersome to use version for C++ that was used to explore high performance parallel JSM induction algorithms and to pick the best data-structures. For a test drive I’m picking the ever so popular <a href="">mushroom data set</a> from UCI.</p> <p>A few words sbout jsm4s - it’s meant to be a flexible library with all manner of tuning but with simple comand-line tool that works out of the box. The cli tool picks non-classic JSM with majority vote predictor and reject by counter-example falsification strategy. As far as encoding goes it detects simple enumerated and numeric fields. For numerics it does a best-effort greedy algorithm to split the value range so that for each piece there is some dominating property value.</p> <p>For simplicity I’ll start with command-line driver, the library itself will allow more flexibility that we do not require. First let’s encode CSV to jsm4s native format:</p> <pre><code>java -jar jsm4s.jar encode -p 0 mushroom.csv mushroom.dat </code></pre> <p>0 indicates that the first column is the desired property. Next randomly split the dataset into training and validation, as 70%/30%:</p> <pre><code>java -jar jsm4s.jar split 7:3 mushroom.dat training.dat validation.dat </code></pre> <p>And make a tau set out of validation to run the classifier on:</p> <pre><code>java -jar jsm4s.jar tau validation.dat tau.dat </code></pre> <p>Now the busy work is done, on to the machine learning, obtain the model (hupotheses):</p> <pre><code>java -jar jsm4s.jar generate -m hypotheses.dat training.dat </code></pre> <p>Finally run the classifier:</p> <pre><code>java -jar jsm4s.jar predict -m hypotheses.dat -o output.dat tau.dat </code></pre> <p>The last two steps could be combined, keeping the model in memory:</p> <pre><code>java -jar jsm4s.jar jsm -o output.dat training.dat tau.dat </code></pre> <p>Okay, time to analyze the results. jsm4s calculates simple metric of correct predictions, conflicts and unknowns.</p> <pre><code>java -jar jsm4s.jar stats validation.dat output.dat </code></pre> <p>There is also another <a href="">dataset</a> that I’ve successfully tested with jsm4s, though it takes a fair amount of time. I hope others might find JSM interesting and will try to apply it to wider range of data. In the age of Deep Learning dominance I think it’s doubly important to keep obscure methods going.</p> Sat, 05 Aug 2017 20:38:00 +0300 jsm ml scala Inside D's GC <p>At the DConf 2017 hackathon I adventurously led a druntime group (of 2 persons) hacking on D’s GC. After a few hours I couldn’t shake off the nagging feeling “boy, this could use a rewrite”. So I decided to start on the quest of better GC for D, the first iteration being faster classic mark-sweep collector.</p> <p>To explain my motivation I’m going to describe the internals of current GC, enumerating issues with the design. All in all, one should analyze what we have to understand where to go from here.</p> <h2 id="pools-pools-everywhere">Pools, pools everywhere</h2> <p>If we were to ignore some global paraphernalia the GC is basically an array of pool objects. Each pool is a chunk of mmap-ed memory + a bunch of malloc-ed metadata such as tables for mark bits, free bits and so on. All allocation happens inside of a pool, if not a single pool is capable to service an allocation a new pool is allocated. The size of a pool is determined by arithmetic progression on the number of pools or 150% of the size of allocation, whatever is bigger.</p> <p>Importantly pools come in two flavors: small object pool and large object pool. Small pools allocate objects up to 2kb in size, the rest is serviced by large pools. Small pools are actually more interesting so let’s look at them first.</p> <p><img src="" alt="Small pool structure" title="Small pool structure" /> Any small allocation is first rounded up to one of power of 2 size classes - 16, 32, 64, 128, 256, 512, 1024, 2048. Then a global freelist for this size class is checked, failing that we go on to locate a small pool. That small pool would allocate a new page and link it up as a free list of objects of this size class. Here comes the first big mistake of the current design - size class is assigned on a page basis, therefore we need a table that maps each page of a pool to a size class (confusingly called pagetable). Now to find the start of an object by internal pointer we first locate the page it belongs to, then lookup the size class, and finally do a bitmask to get to the start of object. More over metadata is a bunch of simple bit-tables that now has to cope with heterogeneous pages, it does so by having ~7 bits per 16 bytes regardless of the object size.</p> <p>What motivated that particular design? I have 2 hypotheses. First is being afraid to reserve memory for underutilized pools, which is a non-issue due to virtual memory with lazy commit. Second is being afraid of having too many pools, slowing down allocation and interestingly marking. The last one is more likely the reason, as indeed GC does a linear scan over pools quite often and a binary search for every potential pointer(!) during the marking phase.</p> <p>That brings us to the second mistake - pool search in logP where P is a number of pools, which makes mark a NlogP business. A hash table could have saved quite a few cycles.</p> <p>Concluding our overview of small pool, we should also look at the selection of size classes. This is a third issue (not a mistake, but controversial choice) having power of 2 sizes guarantees us up to 50% of <a href="">internal fragmentation</a>. Modern allocators such as <a href="">jemalloc</a> typically provide for one more size class in between powers of 2. Modulo by a constant that is not a power of 2 is a bit slower than a single bit AND but still quite affordable.</p> <p><img src="" alt="Large pool structure" title="Large pool structure" /></p> <p>Let’s have a look at large object pools. First thing to note is that its granularity is a memory page (4kb) for both metadata and allocations. Free runs of pages are linked in one free list which is linearly scanned for every allocation request. This is the 4th mistake, that is not bothering with performance of large object allocation at all. To locate a start of an object a separate table is maintained where for every page an index of the start of the object it belongs to is stored. The scheme is sensible until one considers big allocations of 100+ Mb, as it will likely fail to reallocate in place causing a new pool to be allocated and would waste huge amounts of memory on metadata for essentially one object.</p> <h2 id="collection">Collection</h2> <p>So far we observed the allocation pipeline, deallocation follows the same paths. What’s more interesting is automatic reclamation which is the whole point of GC. Let me first dully note that D’s GC is conservative meaning that it doesn’t know if something is a pointer or not, and secondly it supports finalizers, actions that are run on object before reclaiming its memory. These two decisions heavily constrain the design of a collector.</p> <p>From a high level view a collection is surprisingly a whole 4 phase process: <a href="">prepare</a>, <a href="">markAll</a>, <a href="">sweep</a> and <a href="">recover</a>.</p> <p>Prepare stage is the most dubious, essentially it should have been “copy of free bits to mark bits” (to prevent scanning of free memory). The waters are muddied by actually calculating all of free space by walking free lists. This is 5th(?) mistake - leap frogging an additional untold amount of pointers is the last thing to do during stop the world pause. A better design would be flipping free bits during allocation/deallocation, especially since free list maintains pointers to pool for each object so pool search is not required.</p> <p>The actual marking phase is markAll call, that just delegates apropriate ranges of memory to mark function. That <a href="">mark</a> deserves a closer look.</p> <ol> <li>For each pointer in memory range it will first check if it hits the address range of the GC heap (smallest address in a pool to highest address in a pool).</li> <li>Following that a dreaded binary search to find the right pool for the pointer.</li> <li>Regardless of the pool type a lookup into a pagetable for the current pool to see its size class or if it’s a large object or even free memory that is not scanned. There is a tiny optimization in that this lookup also tells us if it’s a start of large object or continuation. We have 3 cases - small object, large object start or large object continuation, the last two are identical save for one extra table lookup.</li> <li>Determining the start of the object - bit masking with the right mask plus in case of large object continuation an offset table lookup.</li> <li>In case of large object there is a “no interior pointer” bit that allows ignoring internal pointers to the object.</li> <li>Finally check and set bit in mark bits, if wasn’t marked before or noscan bit is not set add the object to the stack of memory to scan.</li> </ol> <p>Ignoring the curious stack limiting manipulations (to avoid stack overflow yet try to use the stack allocation) this is all there is to mark function. Apart from already mentioned pool search, deficiencies are still numerous. Mixing no-pointers memory (noscan) with normal memory in the same pool gives us an extra bit-table lookup on hot path. Likewise a pagetable lookup could be easily avoided had we segregated the pools by size class. Not to mention the dubious optimization of no interior pointers bit that not only promotes unsafe code (an object can be collected while still being pointed at) but also introduces a few extra checks on the critical path for all large objects, including a potential bit-table lookup.</p> <p>That was quite involved but keep in mind that mark phase is the heart of any collector. Now to the 3rd phase - sweep. Ironically in current D’s GC sweep doesn’t sweep to free lists as one would expect. Instead all it is concerned about is calling finalizers (if present) and setting free bits and other tables. Bear in mind that this is doing a linear pass through the memory of each pool looking at mark bits.</p> <p>Final stage - recover, this will actually rebuild free lists. It is again a linear pass across pools but only the small ones. Again a pagetable lookup for every page of a pool to learn a size class, it just makes me want to cry. But the main unanswered question is why? Why an extra pass? I tried hard to come up with a reasonable cause but couldn’t, “for simplicity” is a weak but probable explanation. This is the last big mistake by my count.</p> <h2 id="whats-not-there">What’s not there</h2> <p>So far I’ve been criticizing things that are in plain sight, now it’s time to go on to things that are simply non-existent.</p> <p>Thread cache is one big omission, keeping in mind that D’s GC is dated by early 2000s it’s not that surprising. Every modern allocator has some form of thread cache, some try to maintain a per processor cache. A cache works by each thread basically doing allocations in bulk, keeping a stash of allocations for the future. This amortizes the cost of locking the shared data-structures of heap. Speaking of which there is a bit of fine grained locking present, but not say on per pool level.</p> <p>Parallel marking is another example of modern feature that is now totally expected of any garbage collector. Also quite popular are concurrent and mostly concurrent GCs whereby the marking and less often sweep/compaction is done while application threads are running.</p> <h2 id="closing-thoughts">Closing thoughts</h2> <p>The post got pretty lengthy and more involved then I would hope. Still I belive it carries the message across - D’s GC is slow not because of some fundamental limitation but because of a half a dozen or so of bad implementation decisions. In the same vein one could easily build a precise generational GC that is slow, purely missing out on good implementation techniques.</p> <p>Now to sum up what my first iteration attempts to change compared to this baseline.</p> <ul> <li>Segregate small pools on size class.</li> <li>Make O(1) pool search.</li> <li>Try to use more size classes including non-power of 2, a-la jemalloc, to defeat internal fragmentation.</li> <li>Segregate all pools based on no-scan attribute, this streamlines marking.</li> <li>Provide 3rd class of “pools” for huge allocations (16+ Mb) intended for single objects only.</li> <li>Large object pool allocation needs more thought, a kind of tree keyed on block length might be in order. jemalloc uses red-black trees.</li> <li>Drop no interior pointer attribute, it tries to combat false pointers due to conservative GC. However it is fundamentally unsafe and the price is too high, lastly it’s completely pointless on 64-bit systems where your servers are.</li> <li>No whacky multi-phase collection in mark-sweep cycle, it’s mark and sweep, that’s it.</li> <li>Fine grained locking from the start, I see no problem with per pool locking.</li> </ul> <p>The second iteration will focus on more juicy stuff such as thread cache, parallel marking and concurrent marking utilizing the fork trick.</p> <p>The third iteration (if we get to it) would be a completely new design - a mark-region collector with design inspired by <a href="">immix</a>.</p> <p>This concludes my plans and on this optimistic note I will warn that it’s going to start as Linux specific, slowly becoming POSIX specific with Windows support being a distant posibility.</p> Wed, 14 Jun 2017 03:38:00 +0300 gc runtime dlang