[Haskell-cafe] some algorithm help with jhc
lisper at it.kth.se
Wed Sep 14 02:07:46 EDT 2005
>I have started working on jhc more recently and have come across some
>places where I think my algorithms could be improved but was not sure
>exactly where to start so thought I would ask the list since perhaps
>someone here has some insight.
>After a long time of trying various methods of speeding up the fixpoint
>iteration of my points-to analysis (the current main bottleneck) I
>decided to step back and look at the basic problem again. It turns out I
>can express the problem as one of constraint satisfaction resulting in
>much smaller code (600 lines vs 2000) and 10fold speedups with my
>unoptimized first draft solver.
>It is much faster but still not as fast as I'd like. I don't know a lot
>about constraint problems, but my intuiton says this particular problem
>is of a type that should be particularly easy to solve but am uncertain
>where to start in my searching to find a fast algorithm. My constraints
>come in two types of rules.
Hi, check out the book Principles of Program Analysis by Nielson, Nielson,
Hankin (http://www2.imm.dtu.dk/~riis/PPA/ppa.html). It has quite some on
constraint solving for program analysis. There are algorithms in that book
for set constraint problems that look quite similar to your problem.
More information about the Haskell-Cafe