Bug 659 – removeParent() performs very poorly when a parent has >10000 items

PySide Bugzilla Closed for New Bugs

PySide is now a Qt Add-on and uses the Qt Project's JIRA Bug Tracker instead of this Bugzilla instance. This Bugzilla is left for reference purposes.

Bug 659 - removeParent() performs very poorly when a parent has >10000 items

Summary:

removeParent() performs very poorly when a parent has >10000 items

Status:	CLOSED FIXED

Product:	PySide
Classification:	Unclassified
Component:	Shiboken
Version:	1.0.0 beta4
Platform:	All All

Importance:	P3 normal
Assigned To:	renato filho

URL:

Depends on:
Blocks:
	Show dependency tree / graph

Reported:	2011-02-01 21:57 EET by Farsmo
Modified:	2011-02-02 20:05 EET (History)
CC List:	8 users (show)

See Also:

Attachments
untested patch (749 bytes, patch) 2011-02-01 21:57 EET, Farsmo	Details
new patch (1.37 KB, patch) 2011-02-02 12:17 EET, Farsmo	Details
Show Obsolete (1) Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.

Description Farsmo 2011-02-01 21:57:29 EET

Created attachment 245 [details]
untested patch

The patch to bug 556 fixed the performance for setParent(). The bug was caused
by a call to std::find() on ParentInfo::children, which is a std::list. It was
fixed by removing the call to std::find().

Unfortunately, every object that calls setParent() also calls removeParent() on
destruction. And removeParent() suffers from exactly the same performance
issue, but we can't avoid calling erase() on the entry in ParentInfo::children.
Since ParentInfo::children is a std::list we have to look through half the list
(on average) before we know where the entry is.

This could easily be fixed by declaring ParentInfo::children to be a std::set.

Comment 1 Matti Airas 2011-02-02 05:37:13 EET

Thanks for the bug report. I'm prioritizing this P3 (if you'd have time to test
your patch and create a unit test for it, we could apply it right away).

Comment 2 renato filho 2011-02-02 11:41:30 EET

fixed on shiboken commit:

commit 5f09931b15a03b445a47cb837f7ccd864853171b
Author: Renato Araujo Oliveira Filho <renato.filho@openbossa.org>
Date:   Wed Feb 2 09:43:51 2011 -0300


Thanks for the patch

Comment 3 Farsmo 2011-02-02 12:17:29 EET

Created attachment 246 [details]
new patch

Actually it will be much more efficient to keep std::list and add a field to
ParentInfo containing the iterator we need. The ParentInfo itself won't take
more room than the previous solution as a std::list is usually smaller than a
std::set.

I'm not really set up for compiling PySide, so I'm afraid it's untested too.

Comment 4 Farsmo 2011-02-02 12:19:54 EET

Oh sorry, didn't see you already pushed the patch :-o
std::set tends to be pretty heavy, so if you have time to look into it consider
reverting and using the new patch.

Comment 5 Hugo Parente Lima 2011-02-02 14:26:27 EET

(In reply to comment #3)
> Created an attachment (id=246) [details]
> new patch
> 
> Actually it will be much more efficient to keep std::list and add a field to
> ParentInfo containing the iterator we need. The ParentInfo itself won't take
> more room than the previous solution as a std::list is usually smaller than a
> std::set.

We can't store iterators because they may become invalid if the list get
changed.

> I'm not really set up for compiling PySide, so I'm afraid it's untested too.

Renato tested it.

Comment 6 renato filho 2011-02-02 15:46:14 EET

released on beta 5

Comment 7 Farsmo 2011-02-02 20:05:51 EET

(In reply to comment #5)
> We can't store iterators because they may become invalid if the list get
> changed.

std::list guarantees that iterators won't be invalidated by push_back or erase
(except the iterators that point to erased elements), so there shouldn't be any
problem.

> Renato tested it.

Are you referring to the first patch or are you saying that the second patch
doesn't work?