<html> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> </head> <body> <div class="" style="word-wrap:break-word">Hi developers, <div class=""><br class=""> </div> <div class=""> <div class="">I thought I'd send an update on the new LKB's type hierarchy processing. At the beginning of September, I had this running in around 190 secs for Norsyg (norsyg.2018-08-26.tgz) on a mid-range Intel i5 desktop machine. But I convinced myself that it could be better. </div> <div class=""><br class=""> </div> <div class="">In an email of 1 September, Glenn mentions some special configurations of the hierarchy that one can use to speed up processing. I added those he mentions and also a couple of others I think he doesn't. Below are the main steps performed by the LKB and the improvements I made.</div> <div class=""><br class=""> </div> <div class="">* Partition types into non-interacting cliques</div> <div class="">- Removed code that looked for tree-shaped configurations of the hierarchy and excluded them, since a more general case is dealt with below.</div> <div class=""><br class=""> </div> <div class="">* Assign a bit code to each type in the current partition</div> <div class="">- Only assign bit codes to types that are 'active' with respect to GLB computation: an active type has more than 1 parent and/or more than 1 daughter, and is not inside a tree-shaped part of the type hierarchy (i.e. no descendant has more than 1 parent).</div> <div class=""><br class=""> </div> <div class="">* Check pairs of types and create GLB type if no unique common subtype</div> <div class="">- Only check pairs of types that both have more than 1 daughter; other pairs could have a non-unique GLB but this would be found from checks on their descendants.</div> <div class=""><br class=""> </div> <div class="">* Insert GLB types into hierarchy, recomputing parent/daughter links</div> <div class="">- Insert each GLB type sequentially, by checking subsumption relationships with all other 'active' types. The subsumption relation could be in either direction with respect to other GLB types, but for authored types the 'subsume' relation is only relevant to types with more than one parent, and the 'subsumed by' relation only to types with more than one daughter.</div> <div class="">- Fixed the LKB's long-standing redundant links bug by adding a final step to adjust the links from the parents and daughters of each GLB type (fortunately this is pretty cheap).</div> <div class=""><br class=""> </div> <div class="">I also restructured some of the code, and changed a few data structures into more suitable ones, e.g. lists to hash tables.</div> <div class=""><br class=""> </div> <div class="">At this point, I found that 3 "summary" 64-bit words worked best, and Norsyg was down to 120 secs. But I still wasn't happy, and started experimenting first with an index of the first non-zero word in the type bit code, and then an index of the last non-zero word. I don't know why I didn't try this before since the bit codes are so sparse. Taking account of this information in the basic logical operations on bit codes gave a 3x speed up.</div> <div class=""><br class=""> </div> <div class="">It's possible to push this indexing further, and I am also now doing some judicious sorting of lists of types based on their start index so that some highly combinatorial computations can be terminated early. I am also indexing some of these sorted lists in order to start computations in the middle of the list rather than at the beginning. This gives another 2x speed-up. (Interestingly, the summary words now provide much less benefit and I have gone down to just 1 of them (=64 bits) - which is only 15% faster than no summary words at all).</div> <div class=""><br class=""> </div> <div class="">So now the type hierarchy processing for the full Norsyg takes only 20 secs! Here are timings for other grammars:</div> <div class=""><br class=""> </div> <div class="">ERG  0.10 sec</div> <div class="">JACY  0.007 sec</div> <div class="">GG  0.16 sec</div> <div class=""><br class=""> </div> <div class="">The percentage of time taken by each of the steps is:</div> <div class=""><br class=""> </div> <div class="">0.2%  Partition types into non-interacting cliques</div> <div class="">0.8%  Assign a bit code to each type</div> <div class="">26.0%  Check pairs of types and create GLB type if no unique common subtype</div> <div class="">73.0%  Insert GLB types into hierarchy, recomputing parent/daughter links</div> <div class=""><br class=""> </div> <div class="">The first, type partitioning step is cheap but gives modest speed gains: with Norsyg there's an overall 5% speed improvement compared to processing the whole hierarchy at once, and with the ERG there's a 30% improvement.</div> <div class=""><br class=""> </div> <div class="">I attach the LKB source file concerned, which contains more detail in the comments and obviously the full story in the code.</div> <div class=""><br class=""> </div> <div class="">John</div> <div class=""><br class=""> </div> <div class=""><br class=""> </div> <div> <blockquote type="cite" class=""> <div class="">On 1 Sep 2017, at 09:47, John Carroll <<a href="mailto:J.A.Carroll@sussex.ac.uk" class="">J.A.Carroll@sussex.ac.uk</a>> wrote:</div> <br class="x_Apple-interchange-newline"> <div class=""> <div class="" style="word-wrap:break-word">Hi all, <div class=""><br class=""> </div> <div class="">Glenn and I have been exchanging emails off-list about implementation issues in GLB computation and speeding up logical operations on sparse bit vectors. We have also run <i class="">agree</i> and the new version of the LKB on Petter’s whole grammar (see his posting to the list on 26 August). For the benefit of Woodley, Ann and anyone else who’s interested, I append a few excerpts.</div> <div class=""><br class=""> </div> <div class="">John</div> <div class=""><br class=""> </div> <div class=""><br class=""> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> </div> <blockquote type="cite" class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> As I mentioned in my previous note, given a summary qword, I use (x & -x) to directly access, in O(N) of the summary 1 bits, only the interesting qwords. Given such a single-bit mask, I use the 64-bit deBruijn number “0x07EDD5E59A4E28C2” to find its log, so as to index into the main qwords. The code is hairy, but I seem to recall that testing showed large speedups. ... </div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> Glenn</div> </blockquote> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> <br class=""> </div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> </div> </div> <blockquote type="cite" class=""> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> <span class="" style="font-size:11pt">Looks like the</span><span class="" style="font-size:11pt"> </span><i class="" style="font-size:11pt">agree</i><span class="" style="font-size:11pt"> </span><span class="" style="font-size:11pt">results are similar to yours, with a dramatic speedup for computing the glb closure of the full Norwegian type hierarchy that Petter sent (norsyg.2018-08-26.tgz) in about a minute and a half:</span></div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> </div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> 00:00:00 iter 0, glbs: 4943</div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> 00:00:31 iter 1, glbs: 13061</div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> 00:01:15 iter 2, glbs: 7516</div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> 00:01:28 iter 3, glbs: 374</div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> 00:01:28 types:63251 glbs:20951</div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> Best regards,</div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> Glenn</div> </div> </blockquote> <div class=""><br class=""> </div> <div class=""><br class=""> </div> <div class=""> <div class=""></div> </div> <blockquote type="cite" class=""> <div class=""> <div class="">Here are my results for loading Petter’s norsyg.2018-08-26.tgz with the latest LKB:</div> <div class=""><br class=""> </div> <div class="">  grammar        largest partition   time</div> <div class="">  tiny-script    736 types           3 secs</div> <div class="">  small-script   4297 types          17 secs</div> <div class="">  script         40658 types         4 mins 50 secs</div> <div class=""><br class=""> </div> <div class="">For the LKB, the most expensive operation is not computing the glb types but finding the correct place to insert them into the type hierarchy. I’m sure this could be improved.</div> <div class=""><br class=""> </div> <div class="">John</div> </div> </blockquote> <div class=""><br class=""> </div> <div class=""><br class=""> </div> <div class=""><br class=""> <div class=""> <blockquote type="cite" class=""> <div class="">On 28 Aug 2017, at 20:33, Glenn Slayden <<a href="mailto:glenn@thai-language.com" class="">glenn@thai-language.com</a>> wrote:</div> <br class="x_Apple-interchange-newline"> <div class=""> <div class="x_WordSection1" style="font-family:Courier; font-size:12px; font-style:normal; font-weight:normal; letter-spacing:normal; text-align:start; text-indent:0px; text-transform:none; white-space:normal; word-spacing:0px"> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> Thanks John,</div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> Thanks for clarifying how you use wrap-around with your 192-bit scheme to indicate the areas with signal. The reason for my open-ended (auto-expanding) 1:64 ratio system was that I wanted the bitarray implementation to be a general-purpose component that could possibly be used in other sparse-representation applications. Hence also the correct maintaining of the summary bits during arbitrary bitwise operations (indeed some of which they helpfully inform).</div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> I have received your files and will try to load them and report performance figures soon.</div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> Best regards,</div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> GLenn</div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> <div class=""> <div class="" style="border-style:solid none none; border-top-width:1pt; border-top-color:rgb(225,225,225); padding:3pt 0in 0in"> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> <b class="">From:</b><span class="x_Apple-converted-space"> </span>John Carroll [<a href="mailto:J.A.Carroll@sussex.ac.uk" class="">mailto:J.A.Carroll@sussex.ac.uk</a>]<span class="x_Apple-converted-space"> </span><br class=""> <b class="">Sent:</b><span class="x_Apple-converted-space"> </span>Thursday, August 24, 2017 5:42 AM<br class=""> <b class="">To:</b><span class="x_Apple-converted-space"> </span><a href="mailto:developers@delph-in.net" class="">developers@delph-in.net</a><br class=""> <b class="">Cc:</b><span class="x_Apple-converted-space"> </span>Glenn Slayden <<a href="mailto:glenn@thai-language.com" class="">glenn@thai-language.com</a>>; <a href="mailto:gslayden@uw.edu" class="">gslayden@uw.edu</a><br class=""> <b class="">Subject:</b><span class="x_Apple-converted-space"> </span>Re: [developers] speeding up grammar loading in the LKB</div> </div> </div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> Hi Glenn,<span class="x_Apple-converted-space"> </span></div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> A quick follow-up: I like your idea of the summary bits potentially allowing large uninteresting segments of the full bit vectors to be skipped.</div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> I use 192 summary bits (= 3 x 64 bit words) since in my experiments using more bits didn’t give a significant improvement. Although a fixed-size summary representation doesn’t unambiguously identify those words in the full bit vector that are zero, it allows the compiler to unwind loops of logical operations and efficiently inline them.</div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> I’ll be interested in your results with the type files I sent you. (To get the graph I produced cut-down versions by removing final segments of the verbrels.tdl file).</div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> John</div> <p class="x_MsoNormal" style="margin:0in 0in 12pt; font-size:11pt; font-family:Calibri,sans-serif">  </p> <div class=""> <blockquote class="" type="cite" style="margin-top:5pt; margin-bottom:5pt"> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> On 22 Aug 2017, at 23:26, John Carroll <<a href="mailto:J.A.Carroll@sussex.ac.uk" class="" style="color:purple; text-decoration:underline">J.A.Carroll@sussex.ac.uk</a>> wrote:</div> </div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> <div class=""> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> Hi Glenn,<span class="x_Apple-converted-space"> </span></div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> I think my scheme is very similar to yours. Each successive bit in my 192-bit “summary” representation encodes whether the next 64 bits of the full representation has any 1s in it. On reaching the end of the 192 bits, it starts again (so bit zero of the summary also encodes the 193rd group of 64 bits, etc).</div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> I attach the type files. They should be loaded in the following order:</div> </div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> <br class="">  coretypes.tdl<br class="">  extratypes.tdl<br class="">  linktypes.tdl<br class="">  verbrels.tdl<br class="">  reltypes.tdl</div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> John</div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> <div class=""> <blockquote class="" type="cite" style="margin-top:5pt; margin-bottom:5pt"> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> On 22 Aug 2017, at 22:57, Glenn Slayden <<a href="mailto:glenn@thai-language.com" class="" style="color:purple; text-decoration:underline">glenn@thai-language.com</a>> wrote:</div> </div> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> <div class=""> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> Hello All,</div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> I apologize for not communicating this earlier, but since 2009 Agree has used a similar approach of carrying and maintaining supplemental bits, which I call “summary” bits, along with each of the large bit vectors for use during the GLB computation. Instead of a fixed 192 bits, Agree uses one “summary” bit per 64-bit ‘qword’ of main bits, where summary bits are all stored together (allocated in chunks of 64). Each individual summary bit indicates whether it’s corresponding full qword has any 1s in it and is correctly maintained across all logical operations.<span class="x_apple-converted-space"> </span></div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> In the best case of an extreme sparse vector, finding that one summary qword is zero avoids evaluating 4096 bits. More realistically, however, it’s possible to walk the summary bits in O(number-of-set-bits), and this provides direct access to (only) those 64-bit qwords that are interesting.</div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> I would welcome the chance to test Petter’s grammar in Agree.</div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> Best regards,</div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> Glenn</div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> </div> <div class=""> <div class="" style="border-style:solid none none; border-top-width:1pt; border-top-color:rgb(225,225,225); padding:3pt 0in 0in"> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif"> <b class="">From:</b><span class="x_apple-converted-space"> </span><a href="mailto:developers-bounces@emmtee.net" class="" style="color:purple; text-decoration:underline">developers-bounces@emmtee.net</a><span class="x_Apple-converted-space"> </span>[<a href="mailto:developers-bounces@emmtee.net" class="" style="color:purple; text-decoration:underline">mailto:developers-bounces@emmtee.net</a>]<span class="x_apple-converted-space"> </span><b class="">On Behalf Of<span class="x_apple-converted-space"> </span></b>John Carroll<br class=""> <b class="">Sent:</b><span class="x_apple-converted-space"> </span>Friday, August 18, 2017 3:26 PM<br class=""> <b class="">To:</b><span class="x_apple-converted-space"> </span><a href="mailto:developers@delph-in.net" class="" style="color:purple; text-decoration:underline">developers@delph-in.net</a><br class=""> <b class="">Subject:</b><span class="x_apple-converted-space"> </span>Re: [developers] speeding up grammar loading in the LKB</div> </div> </div> </div> <div class=""> <div class="" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">  </div> </div> <div class=""> <div class=""> <p class="x_MsoNormal" style="margin:0in 0in 12pt; font-size:11pt; font-family:Calibri,sans-serif"> <span class="" style="font-size:10pt">Hi,<br class=""> <br class=""> [This is a more detailed follow-up to emails that Petter, Stephan, Woodley and I have been exchanging over the past couple of days]<br class=""> <br class=""> At the very pleasant DELPH-IN Summit last week in Oslo, Petter mentioned to me that the full version of his Norwegian grammar takes hours to load into the LKB. He gave me some of his grammar files, and it turns out that the time is going in computing glb types for a partition of the type hierarchy that contains almost all the types. In this example grammar, there is a partition of almost 40000 types which cannot be split into smaller disjoint sets of non-interacting types. The LKB was having to consider 40000^2/2 (= 800 million) type/type combinations, each combination taking time linear in the number of types. Although this is an efficiently coded part of the LKB, the computation still took around 30 minutes.<br class=""> <br class=""> One fortunate property of the glb type computation algorithm is that very few of the type/type combinations are “interesting” in that they actually lead to creation of a glb. So I came up with a scheme to quickly filter out pairs that could not possibly produce glbs (always erring on the permissive side in order not to make the algorithm incorrect).<br class=""> <br class=""> In this scheme, the bit code representing each type (40000 bits long for this example grammar) is augmented with a relatively short “type filter” code (192 bits empirically gives good results). The two main operations in computing glb types are ANDing pairs of these bit codes and testing whether the result is all zeros, and determining whether one bit code subsumes another (for every zero bit in code 1, the corresponding bit in code 2 must also be zero). By making each bit of a filter code to be the logical OR of a specific set of bits in the corresponding type bit code, the AND and subsume tests can also be applied to these codes as a quick pre-filter.<br class=""> <br class=""> This approach reduces the load time for Petter's example grammar from 30 minutes to 4.5 minutes. It also seems to make the computation scale a bit more happily with increasing numbers of types. I attach a graph showing a comparison for this grammar and cut-down versions.<br class=""> <br class=""> So that grammar writers can benefit soon, Stephan will shortly re-build the LOGON image to include this new algorithm.<br class=""> <br class=""> John</span></p> </div> </div> </div> </blockquote> </div> </div> </div> </div> </blockquote> </div> </div> </div> </div> </blockquote> </div> <br class=""> </div> </div> </div> </blockquote> </div> <br class=""> </div> <div class=""></div> </div> <div class="" style="word-wrap:break-word"> <div class=""></div> <div class=""><br class=""> </div> </div> </body> </html>