From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=unavailable autolearn_force=no version=3.4.4 Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!mx02.eternal-september.org!feeder.eternal-september.org!nntp-feed.chiark.greenend.org.uk!ewrotcd!reality.xs3.de!news.jacob-sparre.dk!loke.jacob-sparre.dk!pnx.dk!.POSTED!not-for-mail From: "Randy Brukardt" Newsgroups: comp.lang.ada Subject: Re: BDD package in Ada. Date: Thu, 9 Apr 2015 19:05:34 -0500 Organization: Jacob Sparre Andersen Research & Innovation Message-ID: References: <44b2e375-8993-4a7e-b81a-6a7b512d2e3e@googlegroups.com> <1miph3v72f4y2$.1u76w2ujg74zf$.dlg@40tude.net> NNTP-Posting-Host: rrsoftware.com X-Trace: loke.gir.dk 1428624334 5822 24.196.82.226 (10 Apr 2015 00:05:34 GMT) X-Complaints-To: news@jacob-sparre.dk NNTP-Posting-Date: Fri, 10 Apr 2015 00:05:34 +0000 (UTC) X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2900.5931 X-RFC2646: Format=Flowed; Response X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.6157 Xref: news.eternal-september.org comp.lang.ada:25503 Date: 2015-04-09T19:05:34-05:00 List-Id: "Georg Bauhaus" wrote in message news:mg5fcg$maf$1@dont-email.me... > On 08.04.15 23:30, Randy Brukardt wrote: >> "Vincent DIEMUNSCH" wrote in message >> news:c7db12c1-10fa-40ee-a2df-ff8a8b2177bc@googlegroups.com... >>> Le mercredi 8 avril 2015 08:38:19 UTC+2, Dmitry A. Kazakov a ?crit : >> >>>> I would not call it "fundamental". It is simply a tree with factored >>>> out >>>> subtrees. Need not to be binary, BTW. >>> A BINARY decision diagram needs to be binary, by definition. It is not >>> "simply" a tree, >>> but a highly optimised data structure, not only by factoring the tree, >>> but >>> through variable >>> ordering, which is the key idea. (Briant's paper is about ORDERED BDD). >>> It >>> is usefull >>> for the implementation of Sets and operations on sets. >> >> Sounds like premature optimization to me. > > The presentations say that in the worst case, some fundamental operations > are O(linear) if the graph is ordered, but are O(exponential) if not. > I am not sure, then, if that makes "premature optimization" an adequate > characterization. That's pretty much the definition of premature optimization. Everything interesting is O(exponential) when you start out. > If a compiler needs to sort out whether or not > something-and-then-this-and-... > -then-if-that...-and-finally-this, then wouldn't the above ordering of > Boolean > trees have a major impact on feasibility? It depends on N. Most N's are small. The Janus/Ada optimizer is (worst-case) O(N**4). It proved to be easier to manage N than to try to redo it to reduce that to a smaller O. Part of the problem of course is that the constant factor matters in practice. If the runtime of the original version is 10*(N**4), but the new version is 1000*(N**2), you will need pretty large Ns before you'll gain anything. In the Janus/Ada case, N (size of a code tree) has to be over 2000 before the runtime becomes noticable to a human. The average N is around 200, only large aggregates or giant case statements give those massive Ns that cause trouble. That's why almost all optimization is premature. I would never have guessed right on the distribution of Ns or what is important in our compiler. I would have wasted time on resolution and other areas whose time was essentially irrelevant. (And I probably did at some point. ;-) The biggest performance problem in our early Ada 95 compilers turned out to be a premature optimization that didn't work (but had a lot of overhead). I only figured that out when I got tired of waiting for a long compilation and stuck a profiler on the appropriate part of the compiler. (I had thought it was doing something useful.) Randy. Randy.