Project

General

Profile

Actions
Copy link

Bug #1831

closed

Stop-sep infrastructure for lattices is slow

Added by Pavel Shved about 13 years ago. Updated about 13 years ago.

Status:
Closed
Priority:
Urgent
Assignee:
Pavel Shved
Category:
-
Target version:
2.7
Start date:
09/26/2011
Due date:
% Done:

0%

Estimated time:
Detected in build:
svn
Platform:
Published in build:

Description

Here's an excerpt from the profile of systemc/token_ring.09.cil.c

      remove all vals               103.711 s (59799)
      add unchanged vals             0.557 s (59799)
      add changed val                0.044 s (59799)
....  
        find_all                      26.585 s (185828)
          find adr_leq                   7.839 s (154836)
            adr_leq_param                  6.896 s (2742975)
              bdd_leq                        1.420 s (2742975)
              lattice.leq                    3.624 s (791122)
              UNACCOUNTED                    1.852 s (26%)
          add                            0.355 s (141681)
          find                           5.269 s (48542)
          exists leq element             0.001 s (13155)

These numbers are inacceptably big, and the inefficiency is caused by a data structure picked for source code compatibility rather than for speed.

We should change the structure to a fast one.

Actions
Copy link
 #1

Updated by Pavel Shved about 13 years ago

  • Status changed from Open to Resolved

Changed the structure to an altered hash table (based on that shipped with the Batteries project) with several faster iteration functions.

But the main bug was that the default OCaml hash function was too imprecise: it didn't traverse too deep into structures, and placed a lot of regions into the same bucket, reducing speed for operations on it. Fixed in f75ea10.

The fix was merged in 85044f6.

Actions
Copy link
 #2

Updated by Pavel Shved about 13 years ago

  • Status changed from Resolved to Closed

This didn't improve our potential score much, but the awful slowdown is gone.

Actions
Copy link

Also available in: Atom PDF