<div dir="ltr">Hi everybody,<div><br></div><div>I apologize for not giving you my whole grammar earlier. I just had to tidy up a little... You can download the grammar files from </div><div><a href="https://www.dropbox.com/s/irucxc313znfmd7/norsyg.2018-08-26.tgz?dl=0">https://www.dropbox.com/s/irucxc313znfmd7/norsyg.2018-08-26.tgz?dl=0</a></div><div>The grammar now loads with both LKB (lkb/script) and ACE (ace/config.tdl). The last time I loaded it with ACE, the checking of glb types took 4 hours. I am curious to hear if it also loads with Agree. If you want to test with smaller versions of the grammar, you can load it with lkb/small-script or lkb/tiny-script, alternatively ace/config-small.tdl or ace/config-tiny.tdl. </div><div><br></div><div>Best,</div><div><br></div><div>Petter</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Aug 24, 2017 at 2:42 PM, John Carroll <span dir="ltr"><<a href="mailto:J.A.Carroll@sussex.ac.uk" target="_blank">J.A.Carroll@sussex.ac.uk</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> <div style="word-wrap:break-word"> Hi Glenn, <div><br> </div> <div>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><br> </div> <div>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><br> </div> <div>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><br> </div> <div>John<br> <div></div> <br> <br> <div> <blockquote type="cite"> <div>On 22 Aug 2017, at 23:26, John Carroll <<a href="mailto:J.A.Carroll@sussex.ac.uk" target="_blank">J.A.Carroll@sussex.ac.uk</a>> wrote:</div> <br class="m_-2406462820371682377Apple-interchange-newline"> <div> <div style="word-wrap:break-word"> Hi Glenn, <div><br> </div> <div>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><br> </div> <div>I attach the type files. They should be loaded in the following order:</div><span class=""> <br> coretypes.tdl<br> extratypes.tdl<br> linktypes.tdl<br> verbrels.tdl<br> reltypes.tdl<br> <div><br> </div> </span><div>John</div><div><div class="h5"> <div><br> </div> <div><br> <div> <blockquote type="cite"> <div>On 22 Aug 2017, at 22:57, Glenn Slayden <<a href="mailto:glenn@thai-language.com" target="_blank">glenn@thai-language.com</a>> wrote:</div> <br class="m_-2406462820371682377Apple-interchange-newline"> <div> <div class="m_-2406462820371682377WordSection1" style="font-family:Courier;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"> <div style="margin:0in 0in 0.0001pt;font-size:11pt;font-family:Calibri,sans-serif"> Hello All,<u></u><u></u></div> <div style="margin:0in 0in 0.0001pt;font-size:11pt;font-family:Calibri,sans-serif"> <u></u> <u></u></div> <div 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="m_-2406462820371682377Apple-converted-space"> </span><u></u><u></u></div> <div style="margin:0in 0in 0.0001pt;font-size:11pt;font-family:Calibri,sans-serif"> <u></u> <u></u></div> <div 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.<u></u><u></u></div> <div style="margin:0in 0in 0.0001pt;font-size:11pt;font-family:Calibri,sans-serif"> <u></u> <u></u></div> <div 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.<u></u><u></u></div> <div style="margin:0in 0in 0.0001pt;font-size:11pt;font-family:Calibri,sans-serif"> <u></u> <u></u></div> <div style="margin:0in 0in 0.0001pt;font-size:11pt;font-family:Calibri,sans-serif"> Best regards,<u></u><u></u></div> <div style="margin:0in 0in 0.0001pt;font-size:11pt;font-family:Calibri,sans-serif"> <u></u> <u></u></div> <div style="margin:0in 0in 0.0001pt;font-size:11pt;font-family:Calibri,sans-serif"> Glenn<u></u><u></u></div> <div style="margin:0in 0in 0.0001pt;font-size:11pt;font-family:Calibri,sans-serif"> <u></u> <u></u></div> <div style="margin:0in 0in 0.0001pt;font-size:11pt;font-family:Calibri,sans-serif"> <u></u> <u></u></div> <div style="margin:0in 0in 0.0001pt;font-size:11pt;font-family:Calibri,sans-serif"> <u></u> <u></u></div> <div> <div style="border-style:solid none none;border-top-width:1pt;border-top-color:rgb(225,225,225);padding:3pt 0in 0in"> <div style="margin:0in 0in 0.0001pt;font-size:11pt;font-family:Calibri,sans-serif"> <b>From:</b><span class="m_-2406462820371682377Apple-converted-space"> </span><a href="mailto:developers-bounces@emmtee.net" target="_blank">developers-bounces@<wbr>emmtee.net</a> [<a href="mailto:developers-bounces@emmtee.net" target="_blank">mailto:developers-bounces@<wbr>emmtee.net</a>]<span class="m_-2406462820371682377Apple-converted-space"> </span><b>On Behalf Of<span class="m_-2406462820371682377Apple-converted-space"> </span></b>John Carroll<br> <b>Sent:</b><span class="m_-2406462820371682377Apple-converted-space"> </span>Friday, August 18, 2017 3:26 PM<br> <b>To:</b><span class="m_-2406462820371682377Apple-converted-space"> </span><a href="mailto:developers@delph-in.net" target="_blank">developers@delph-in.net</a><br> <b>Subject:</b><span class="m_-2406462820371682377Apple-converted-space"> </span>Re: [developers] speeding up grammar loading in the LKB<u></u><u></u></div> </div> </div> <div style="margin:0in 0in 0.0001pt;font-size:11pt;font-family:Calibri,sans-serif"> <u></u> <u></u></div> <div> <div> <p class="MsoNormal" style="margin:0in 0in 12pt;font-size:11pt;font-family:Calibri,sans-serif"> <span style="font-size:10pt">Hi,<br> <br> [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> <br> 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> <br> 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> <br> 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> <br> 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> <br> So that grammar writers can benefit soon, Stephan will shortly re-build the LOGON image to include this new algorithm.<br> <br> John</span></p> </div> </div> </div> </div> </blockquote> </div> </div> </div></div></div> </div> </blockquote> </div> <br> </div> </div> </blockquote></div><br></div>