https://bugs.documentfoundation.org/show_bug.cgi?id=150064
Michael Weghorn <[email protected]> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |[email protected] Assignee|[email protected] |[email protected] | |desktop.org Keywords| |bibisected, bisected, | |regression Regression By| |Noel Grandin | |<[email protected]. | |uk> Status|ASSIGNED |NEW --- Comment #4 from Michael Weghorn <[email protected]> --- (In reply to Michael Weghorn from comment #3) > Might be a regression from > > commit 8f9fd6806ccfbf381a383efe5d143ead86ee49de > Date: Wed Jun 29 19:47:20 2022 +0200 > > tdf#137544 reduce cost of ChildrenManagerImpl::Update > > there are 2 O(n^2) algorithms here, reduce them to O(n log n) by > pre-sorting > > Change-Id: Ib3912155cda62cac95b5037528e23ef3c686a7e8 > Reviewed-on: https://gerrit.libreoffice.org/c/core/+/136655 > Tested-by: Jenkins > > I'll look into it a little closer myself first to see whether it's actually > a regression and whether any good ideas come to mind rather quickly while > doing so. It's actually a regression from that commit, the test works fine for me with a local revert. The only idea I can currently come up with to not revert back to the previous O(n^2) behavior would be to allocate another helper vector (with pointers to the items in the "real vector") and sort only that one, while leaving the original vector of children unchanged. If that makes any sense, I could come up with a change for that, but I don't know whether that would be a performance gain as compared to the O(n^2) looping in the end, or the extra vector allocation outweighs that. (I don't have much experience with performance optimization and the test file from tdf#137544 takes so long to open with my debug build that it discourages from doing more extensive experiments...) Adding CC: to Noel Grandin: Any ideas/suggestions? -- You are receiving this mail because: You are the assignee for the bug.
