Project

General

Profile

[logo] 
 
Home
News
Activity
About/Contact
Major Tools
  Dinotrace
  Verilator
  Verilog-mode
  Verilog-Perl
Other Tools
  BugVise
  CovVise
  Force-Gate-Sim
  Gspice
  IPC::Locker
  Rsvn
  SVN::S4
  Voneline
  WFH
General Info
  Papers

Issue #1090

iterating over duplicate nodes in V3Trace is slow

Added by Johan Bjork 11 months ago. Updated 10 months ago.

Status:
Closed
Priority:
Normal
Assignee:
Category:
TranslationError
% Done:

0%


Description

finding the 'master' duplicate node in V3Trace.cpp:assignTraceCode(...) is very slow on large designs as the number of duplicated nodes can be very large (On one of our designs I see iterations of up to 21000 nodes!)

History

#1 Updated by Wilson Snyder 11 months ago

That code does use a hash table, so it should be O(n). I wrote a hacky script that did 100,000 duplicates and it was in 110th place in profiling, so I'll need more hints as to what is slow.

#2 Updated by Johan Bjork 11 months ago

Wilson Snyder wrote:

That code does use a hash table, so it should be O(n). I wrote a hacky script that did 100,000 duplicates and it was in 110th place in profiling, so I'll need more hints as to what is slow.

The problem is not in the code that calculates the duplicates (that does use a hash map), but in the code that assigns the trace code. This loop:
    while (dupvertexp->duplicatep()) {
        dupvertexp = dupvertexp->duplicatep();
        UINFO(9,"   dupOf "<<((void*)dupvertexp)<<" "<<((void*)dupvertexp->nodep())
          <<" "<<dupvertexp<<endl);
    }
If you can't reproduce it easily, I'll try and find some time this weekend to write a patch. I don't have our project in front of me right now, but for us it's by far the main culprit in performance when building, accounting for ~20seconds out of 119.

#3 Updated by Wilson Snyder 11 months ago

  • Status changed from New to AskedReporter

Hmm, perhaps try changing that code so that as it follows the list, it updates the previous entries so they point right to the last entry, so the list never needs to be followed again. See if that helps your case please.

#4 Updated by Johan Bjork 11 months ago

Wilson Snyder wrote:

Hmm, perhaps try changing that code so that as it follows the list, it updates the previous entries so they point right to the last entry, so the list never needs to be followed again. See if that helps your case please.

How about something like this? https://github.com/phb/verilator-dev/commit/bc3c2b74604502f8eac58bfb238bbfbabdd76ca2

#5 Updated by Wilson Snyder 11 months ago

  • Category set to TranslationError
  • Status changed from AskedReporter to Resolved
  • Assignee set to Johan Bjork

Great, pushed to git towards 3.888.

#6 Updated by Wilson Snyder 10 months ago

  • Status changed from Resolved to Closed

In 3.888 (on 2016-10-14).

Also available in: Atom