Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2016-09-16T22:13:10Z

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.

Original Redmine Comment
Author Name: Johan Bjork
Original Date: 2016-09-16T22:56:26Z

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.

Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2016-09-16T23:30:41Z

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.

Original Redmine Comment
Author Name: Johan Bjork
Original Date: 2016-09-17T20:08:32Z

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?
phb/verilator-dev@bc3c2b7

Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2016-09-19T21:56:39Z

Great, pushed to git towards 3.888.

Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2016-11-05T12:51:38Z

In 3.888 (on 2016-10-14).