Here are the top three offenders when deleting ~10000 clones:
% cumulative self self total time seconds seconds calls s/call s/call name 26.42 35.29 35.29 50000 0.00 0.00 sp_object_get_child_by_repr(SPObject*, Inkscape::XML::Node*) 14.10 54.12 18.83 9999 0.00 0.00 sp_item_pos_in_parent(SPItem*) 11.45 69.42 15.30 20003 0.00 0.00 SPSelection::_removeObjectDescendants(SPObject*)
They're also the only ones that individually accounted for > 10% of the CPU time, and together these three account for 51% of the entire time.
Surprised me, actually; sp_repr_prev() only showed up at 7%, and it was only called 10000 times. So that means my speculations last night were largely wrong. But I guess this is a good illustration (for those following along at home) why it's good to profile rather than assume. ^^;
But anyway... pondering how best to optimize things now. Suggestions welcome. I'm a bit reluctant to do the obvious and have every SPObject keep e.g. a hashtable of Node/SPObject mappings for its children, as that would come at a very heavy memory cost.
At least for _removeObjectDescendants and sp_object_get_child_by_repr(), we may also be able to call them less in the first place...
-mental