Perl 6 - the future is here, just unevenly distributed

IRC log for #marpa, 2014-07-31

| Channels | #marpa index | Today | | Search | Google Search | Plain-Text | summary

All times shown according to UTC.

Time Nick Message
02:30 jeffreykegler joined #marpa
11:13 jdurand joined #marpa
11:13 jdurand FYI, I just came up on a what I think is a remarquable resume of all data structures in computing, c.f. http://adityacse.weebly.com/uploads/​2/4/0/7/24078687/data-structures.pdf - if that could be of interest for Marpa internal, who knows -; !
11:45 ronsavage jdurand: I'll bet generations of computer science students would have loved to have that doc available. I sure would have.
16:37 jeffreykegler joined #marpa
16:38 jeffreykegler judrand: interesting book -- no author/editor given -- it looks like a compilation of Wikipedia articles.
16:39 jeffreykegler It is interesting that of the many data structures possible, only a few receive 99.99% of the usage.  Most have not much of a track record.
16:41 jeffreykegler One thing I've picked up from the Stpehanov videos -- the relative efficiency of algorithms and data structures has changed.  Originally, the number of instructions governed efficiency.  Now that count is basically irrelevant
16:42 jeffreykegler IT's now all about cache misses -- and that changes winners into losers and vice versa.
17:02 jdurand joined #marpa
17:04 jeffreykegler I suppose it's the same for parsing -- people don't consider all the algorithms out there -- there's a short list everyone talks about, and rules of thumb (and often just plain old fashion and crowd behavior) dictate almost all of the choices.
17:04 jdurand Re http://irclog.perlgeek.de/​marpa/2014-07-31#i_9113568 - you are right - this is exactly for example what has adressed an alternative implementation of B+tree in C++, c.f. http://panthema.net/2007/stx-btree/ - and the numbers speak themselves, it is much faster - this is what I am looking for in the C world
17:05 jdurand and I dunno if GNU libavl has such optimisation, yet -;
17:05 jeffreykegler AVL'
17:05 jeffreykegler What's the optimization?  AVL's are very different from B-trees.
17:06 jdurand I am talking about using memory caches by forcing alignment of data in memory
17:06 jeffreykegler That's not in AVL's "blood"
17:07 jeffreykegler B-trees are all about blocks with nice behavior.
17:07 jeffreykegler When that becomes the game, AVL's have lost the race before the starting gun fires.
17:07 jeffreykegler Btw, speaking of races.
17:08 jdurand Yes, usually in-memory b-tree may/should outperform others because of native alignment - agreed
17:08 jeffreykegler It'd be interesting to see Marpa's AVL's set against Lua's tables sometime.
17:09 jdurand yep!
17:10 jeffreykegler If I were doing it over, I think I'd just adopt Lua's tables as Marpa's data structure, but the effort to put in AVL's is a "sunk cost" at this point.
17:11 jeffreykegler Note that Lua's tables have a problem, in that (in common with hashes) it's impossible to treat the keys in sorted order.
17:11 jdurand Ah, ok did not know
17:12 jeffreykegler (There's an exception for Lua tables which are sequences, 1, 2, ..., where Lua uses a mixed strategy.)
17:12 jdurand but is that needed for Marpa - in fact the most important thing is, forgive me if I am wrong, a generatic stack layer isn't it
17:12 jeffreykegler AVL's can easily be traversed in sorted order.
17:12 jdurand generic
17:12 jeffreykegler I didn't understand the question
17:13 jeffreykegler Was it, does Marpa really need traversal in sorted order?
17:14 jdurand I zqs making some distinction between lexing and value phases
17:14 jdurand "was"
17:15 jeffreykegler Marpa's uses AVL's for all sorts of internal stuff, and traversal in sorted order is very handy.
17:15 jeffreykegler And that's in all phases.
17:15 jdurand and wondered if both phases are not, after all, just generic a generic stack layer: context is a stack, providing parse tree value is also a stack - ok; so you use an AVL to provide you stack layer, that is your VM
17:16 jdurand "after all, just using a generic stack layer"
17:17 jeffreykegler For the major data structures in Marpa, I do it on a customized case-by-case basis.
17:17 jeffreykegler The evaluation stack IIRC is a pre-sized dynamic array.
17:19 jeffreykegler The Earley tables are linked lists of arrays, with an indexing array calculated once they are finished, and the number of Earley sets is a known constant.
17:19 jdurand ok
17:20 jeffreykegler In that sense, AVL versus hash inside Marpa is not a big deal ...
17:20 jdurand I see
17:21 jeffreykegler because the high cost data structures are customized on a case by case basis.
17:21 jdurand once you said that getting the context of a previous G1 location can have a big cost - why ? Is that the search of the index in linked list of arrays
17:21 jeffreykegler And AVL's are just a "utility" data structure.
17:22 jeffreykegler I forget the context -- and which SLIF version we were talking about also would make a difference.
17:23 jeffreykegler Were we talking about progress reports?
17:23 jdurand Yes -;
17:23 jeffreykegler In that case, finding the Earley table was not the problem -- that was fast.
17:24 jeffreykegler I* Earley table -> Earley set
17:24 jeffreykegler It's that the Earley tables were optimized only for parsing and evaluation needs.
17:25 jeffreykegler The "full picture" required by a progress report, including unraveling the internal forms of rules and symbols into their external equivalents ...
17:25 jdurand ok
17:26 jeffreykegler required a re-examination of the Earley set, which in fact involved IIRC correctly, building one AVL tree for each Earley set.
17:27 jeffreykegler You might compare heavy use of progress reports with use of the debugger as a programming technique.
17:27 jdurand ok - many thanks for the explanation - have to afk -; I let you tell if you managed to install latest version of luajit on your ubuntu! see you later
17:28 jeffreykegler I overwrote my MBR in the process, but yes I got luajit going.
17:28 jeffreykegler I screwed up the packaging, and wound up removing grub, which wrecked my Master Boot Record.
17:29 jeffreykegler Which I managed to restore.
17:29 jeffreykegler jdurand: bye!
21:56 jeffreykegler joined #marpa

| Channels | #marpa index | Today | | Search | Google Search | Plain-Text | summary