Re: [Chicken-hackers] [PATCH] fix #1648 (correctly)
> > Pushed. Thanks! and thanks for fixing the comment and your note about O(N) performance. I don't think it makes much of a difference in real life to use a different data structure, but nevertheless it is noted for posterity. felix ___ Chicken-hackers mailing list Chicken-hackers@nongnu.org https://lists.nongnu.org/mailman/listinfo/chicken-hackers
Re: [Chicken-hackers] [PATCH] fix #1648 (correctly)
Pushed. Thanks! ___ Chicken-hackers mailing list Chicken-hackers@nongnu.org https://lists.nongnu.org/mailman/listinfo/chicken-hackers
Re: [Chicken-hackers] [PATCH] fix #1648 (correctly)
> >Left as an exercise to you, dear reader. A singly-linked list is > >simple and straightforward, I find hash-tables ugly and wasteful > >and will wory about scalability when the time arrives. > > IMHO single linked lists do have one drawback: they encode the assumption > of a specific from of the mapping right into the code. When finally the > time arrives, the code is usually hard to change. Especially if one does > not know what exactly the code should do and why a linked list was chosen > in the first place. I do not disagree in principle, but in this particular case, the list is both the natural and (relatively) efficient solution. The idea is to push every inlining-pair (identifiers for caller + callee) as a cons onto the list and count the number of occurrences when walking the list for every new pair. It represents the inling history directly as it reflects the relative order of inlinings. The list is accessed only twice, once in the search/test and once when pushing a new pair onto the history, so if one is inclined to change the representation, it shouldn't be too hard. The performance penalty for searching the list is in the subsecond area in my tests (DEBUGBUILD, compiling irregex-core.scm), comparing a version with the list-search and the current HEAD, irregex-core.scm has about 1500 inlined procedures. > > I for one, tend to use balanced trees instead of plain lists when I worry > about the downsides of hash tables (about those latter I share your view > Felix) and still want to have obvious and clear code and retain the ability > to change the implementation. Balanced trees are nice, but have to be coded with care. In this case it would probably not make a difference, unless run on files with a pathological number of inline cases. So the simplest solution here seems to be sufficient in terms of speed, minimal in terms of storage used and easiest in terms of maintenance. That looks appropriate to me. felix ___ Chicken-hackers mailing list Chicken-hackers@nongnu.org https://lists.nongnu.org/mailman/listinfo/chicken-hackers
Re: [Chicken-hackers] [PATCH] fix #1648 (correctly)
On Oct 1 2019, felix.winkelm...@bevuta.com wrote: I don't think the -unroll-limit is that useful option to expose for the user. The -inline-limit already controls the amount of inlining. I couldn't get anything to unroll more than once without having to increase the inline-limit, which of course has other implications. The inline-limit considers the _size_ of a procedure to be inlined. The unroll-limit specifies the _number_ of times an inlinable procedure will actually be inlined at the same call site. I agree that the declaration/option is of limited use, but it's consisten with the declarations/options we have. This is unnecessarily O(n^2) in the number of performed inlines. I think we should use a hash-table for inline-history. I tested with some generated files and the results were: Case n=100: real0m1.784s vs. real 0m2.179s (1.2x) Case n=200: real0m7.495s vs. real 0m12.235s (1.6x) Case n=300: real0m17.738s vs. real 0m42.660s (2.4x) Case n=400: real0m34.975s vs. real 2m3.604s (3.5x) Left as an exercise to you, dear reader. A singly-linked list is simple and straightforward, I find hash-tables ugly and wasteful and will wory about scalability when the time arrives. IMHO single linked lists do have one drawback: they encode the assumption of a specific from of the mapping right into the code. When finally the time arrives, the code is usually hard to change. Especially if one does not know what exactly the code should do and why a linked list was chosen in the first place. I for one, tend to use balanced trees instead of plain lists when I worry about the downsides of hash tables (about those latter I share your view Felix) and still want to have obvious and clear code and retain the ability to change the implementation. So let me suggest to at least not hard code list traversals. /Jörg ___ Chicken-hackers mailing list Chicken-hackers@nongnu.org https://lists.nongnu.org/mailman/listinfo/chicken-hackers
Re: [Chicken-hackers] [PATCH] fix #1648 (correctly)
> I don't think the -unroll-limit is that useful option to expose for the > user. The -inline-limit already controls the amount of inlining. I > couldn't get anything to unroll more than once without having to > increase the inline-limit, which of course has other implications. The inline-limit considers the _size_ of a procedure to be inlined. The unroll-limit specifies the _number_ of times an inlinable procedure will actually be inlined at the same call site. I agree that the declaration/option is of limited use, but it's consisten with the declarations/options we have. > This is unnecessarily O(n^2) in the number of performed inlines. I think > we should use a hash-table for inline-history. > > I tested with some generated files and the results were: > > Case n=100: real 0m1.784s vs. real 0m2.179s (1.2x) > Case n=200: real 0m7.495s vs. real 0m12.235s (1.6x) > Case n=300: real 0m17.738s vs. real 0m42.660s (2.4x) > Case n=400: real 0m34.975s vs. real 2m3.604s (3.5x) Left as an exercise to you, dear reader. A singly-linked list is simple and straightforward, I find hash-tables ugly and wasteful and will wory about scalability when the time arrives. felix ___ Chicken-hackers mailing list Chicken-hackers@nongnu.org https://lists.nongnu.org/mailman/listinfo/chicken-hackers
Re: [Chicken-hackers] [PATCH] fix #1648 (correctly)
Hi, I took a look at this. Four points: 1. It fixes the runaway inlining. \o/ 2. I don't think the -unroll-limit is that useful option to expose for the user. The -inline-limit already controls the amount of inlining. I couldn't get anything to unroll more than once without having to increase the inline-limit, which of course has other implications. (Here I digress.. This made me wonder why didn't -inline-limit stop the unrolling in the first place? I think the reason is that after the lambda is inlined with inline-lambda-bindings the size of the lambda is not updated. Maybe this could cause too big inlinings if the inlines are nesting? ) felix.winkelm...@bevuta.com writes: > From 5f0aec415b782023f9827b8ce14e499b148a335a Mon Sep 17 00:00:00 2001 > From: felix > Date: Wed, 18 Sep 2019 14:36:55 +0200 > Subject: [PATCH] Catch runaway inlining > [...] > > > +;; Check whether inlined procedure has already been inlined in the > +;; same target procedure and count occurrences. If the number of > +;; inlinings exceed the unroll-limit 3. The documentation cuts off abruptly here. > + > +(define (within-unrolling-limit fid tfid max-unrolls) > + (let ((p (cons fid tfid))) > +(let loop ((h inline-history) (n 0)) > + (cond ((null? h)) > +((equal? p (car h)) > + (and (< n max-unrolls) > + (loop (cdr h) (add1 n > +(else (loop (cdr h) n)) > + 4. This is unnecessarily O(n^2) in the number of performed inlines. I think we should use a hash-table for inline-history. I tested with some generated files and the results were: Case n=100: real0m1.784s vs. real 0m2.179s (1.2x) Case n=200: real0m7.495s vs. real 0m12.235s (1.6x) Case n=300: real0m17.738s vs. real 0m42.660s (2.4x) Case n=400: real0m34.975s vs. real 2m3.604s (3.5x) ___ Chicken-hackers mailing list Chicken-hackers@nongnu.org https://lists.nongnu.org/mailman/listinfo/chicken-hackers
