Paul Gilmartin wrote: <begin extract> Which might be the proper implementation if the cases are sparse. Best to start with the median case value and bisect recursively. Storage is cheap nowadays, particularly if it's not accessed. But a large and sparse branch table is an invitation to page faults. </end extract>
I must admit that I am not quite sure what this means. The obvious interpretation is precluded. Compilers--unlike, say, RDBMs--are not ordinarily provided with frequency statistics for case values. If instead it means that a BST can be used to replace a polynomial-time linear-search scheme with an exponential-time binary-search one, I agree. Where it can be used, a branch table is nevertheless a very much better alternative. An example will help here. The American insurance industry is licensed and regulated chiefly, by the individual states, with New York State occupying the position of primus inter pares for historical reasons. Underwriting rules thus differ from state, and not just premium rates but even such minutiæ as penny-breakage rules are different from one state to another. In the upshot the industry has historically made much use of nested-if of the generic form if state-code is 'AL' then . . . else if state-code is 'AK' then . . . else if state-code is 'AR' then . . . else if state-code is 'AZ' then . . . . . . else if state-code is 'DC' then . . . . . . else if state-code is 'PR' then . . . . . else if state-code is 'WV' then . . . else if state-code us 'WY' then . . . else <error sink> which often occur multiply in the same routine. (I have in my black museum a a routine that contains 127 instances of this scheme.) A single branch-table replacement for these schemes requires a very sparse page-aligned table of 2^16 = 65536 bytes and 1992 bytes of very simple rentrant LE-compatible HLASM code. The table thus occupies 16 4k-byte pages, and careful instrumentation---I was anxious to establish performance benefits---showed that the branch-table scheme wax more than 8000 (sic) times faster than the nested-ifs even after the nested-if seq. Non-transient paging was looked for but not found. There is a tendency to react to TRTO-based schemes---OMG, a 64k table!---with the gut rather than the brain John Gilmore, Ashland, MA 01721 - USA ---------------------------------------------------------------------- For IBM-MAIN subscribe / signoff / archive access instructions, send email to lists...@listserv.ua.edu with the message: INFO IBM-MAIN
