13 Dec 1997 12:02:30 -0500

Related articles |
---|

Compact transition matrix storage schemes pprakash@mail.tea.state.tx.us (Praki Prakash) (1997-12-12) |

Re: Compact transition matrix storage schemes chase@world.std.com (David Chase) (1997-12-13) |

Re: Compact transition matrix storage schemes hbaker@netcom.com (1997-12-14) |

Re: Compact transition matrix storage schemes mtimmerm@microstar.no-spam.com (Matt Timmermans) (1997-12-15) |

Re: Compact transition matrix storage schemes autom@earthlink.net (Paul Mann) (1997-12-23) |

From: | David Chase <chase@world.std.com> |

Newsgroups: | comp.compilers |

Date: | 13 Dec 1997 12:02:30 -0500 |

Organization: | Natural Bridge LLC |

References: | 97-12-086 |

Keywords: | practice |

Praki Prakash wrote:

*> Can anybody point me to some published literature on the various schemes*

*> for storing transition matrix? I have done a bibliographic search but*

*> did not see any.*

*> [There's a little bit in the Dragon Book, but the approaches I've seen are*

*> all rather ad-hoc. -John]*

This has come up from time to time in the code generation world.

There's the smash-out-equal-columns-and-rows stunt that has been

around for a long time. I had a paper in the 1987 POPL that described

a way to automatically construct pre-smashed tables for bottom-up tree

pattern matching (this was considered interesting because the

unsmashed tables can be extravagantly large, even on today's hardware,

never mind what we were using ten years ago). Fraser and Henry (?)

had a paper in Software Practice and Experience that explored several

heuristics for further reducing the space taken by these table while

still generating code very quickly.

I once tinkered with a run-length-encoded form of table storage; the

idea here is to permute columns so that the least number of equal runs

are created over all the rows; that is, it is better to have

0 0 0 0 0 0 1 1 1 1 1 1

than

0 1 0 1 0 1 0 1 0 1 0 1

Life gets more interesting when you have more than one row.

Turns out that finding the optimal permutation is an NP-complete

problem. It's relatively easy to turn it into a weird version of

traveling salesperson, where each column corresponds to a city and the

distance between two cities is the number of unequal elements.

Finding a shortest-cost route (using that definition of distance)

gives you your permutation. This is useful, since people have spent a

fair amount of time trying to get good heuristics for TS. (I don't

recall the other half of the NP-completeness proof, but I think you

can see it isn't hard). I think I used a heuristic described in Garey

and Johnson that involved a min-cost spanning tree plus some sort of a

matching heuristic, and I think it worked well, but this was never

published.

--

David Chase, chase@world.std.com

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.