Bug 94262 - LibO freezes when trying to open styles and formatting menu (F11)
Summary: LibO freezes when trying to open styles and formatting menu (F11)
Alias: None
Product: LibreOffice
Classification: Unclassified
Component: Calc (show other bugs)
(earliest affected) release
Hardware: Other All
: medium major
Assignee: Aron Budea
Whiteboard: target:5.3.0
Keywords: perf
Depends on:
Reported: 2015-09-16 09:40 UTC by Xisco Faulí
Modified: 2016-11-14 15:45 UTC (History)
3 users (show)

See Also:
Crash report or crash signature:

.xls sample (3.81 MB, application/vnd.ms-excel)
2016-10-26 07:15 UTC, Xisco Faulí

Note You need to log in before you can comment on or make changes to this bug.
Description Xisco Faulí 2015-09-16 09:40:13 UTC
Steps to reproduce:
1. Open attachment 106004 [details] from bug 83684
2. Press F11 to open 'styles and formatting' menu

Observed behavior: Libreoffice freezes.

Reproduced with

Build ID: 81898c9f5c0d43f3473ba111d7b351050be20261
Locale: es-ES (es_ES)

on Windows 7 (64-bit)
Comment 1 tommy27 2015-09-17 05:02:11 UTC
I reproduce the bug under Win8.1 x64 using LibO and a recent LibO 5.1.0 alpha daily build.

file can't be opened in LibO 4.3.x because of bug 83684
Comment 2 QA Administrators 2016-09-20 10:32:49 UTC Comment hidden (obsolete)
Comment 3 Xisco Faulí 2016-10-26 07:02:15 UTC
This issue is still reproducible in

Build ID: 8974b0fafb18f9dd3f2c0e175a3255b80e4c249e
CPU Threads: 4; OS Version: Linux 4.2; UI Render: default; 
Locale: ca-ES (ca_ES.UTF-8); Calc: group
Comment 4 Xisco Faulí 2016-10-26 07:15:28 UTC
Created attachment 128273 [details]
.xls sample

Same result in .XLS
Comment 5 Aron Budea 2016-11-10 00:26:33 UTC
(In reply to Xisco Faulí from comment #4)
> Created attachment 128273 [details]
> .xls sample
> Same result in .XLS

Apparently the file contains 32572 styles, and this function is quadratic because of the two nested for-loops:

StyleTreeArr_Impl& MakeTree_Impl(StyleTreeArr_Impl& rArr)
Comment 6 Aron Budea 2016-11-10 00:28:01 UTC
Three nested for-loops, actually...
Comment 7 Xisco Faulí 2016-11-10 02:00:57 UTC
Probably the array can be replaced by a std::map instead?
Comment 8 Aron Budea 2016-11-10 06:06:51 UTC
Yes, I thought of something similar, I'm using a helper unordered_map with style name and pointer to style. That gets rid of the second-level for-loop (linear -> const access).

The innermost for-loop is being replaced with an std::lower_bound, since it always tries to insert in a sorted array (linear -> log access).
Comment 9 Commit Notification 2016-11-14 09:49:36 UTC
Aron Budea committed a patch related to this issue.
It has been pushed to "master":


tdf#94262: fix performance of MakeTree_Impl(...) in templdlg.cxx

It will be available in 5.3.0.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:

Affected users are encouraged to test the fix and report feedback.
Comment 10 Xisco Faulí 2016-11-14 12:23:44 UTC
fix verified in

Build ID: 757a60d01dd152aadab2ba3c8224252481ce8a88
CPU Threads: 4; OS Version: Linux 4.8; UI Render: default; VCL: gtk2; Layout Engine: new; 
Locale: ca-ES (ca_ES.UTF-8); Calc: group

@Aron, you can close it as RESOLVED VERIFIED
Comment 11 Aron Budea 2016-11-14 15:41:34 UTC
Great, thanks for the verification.
Comment 12 Aron Budea 2016-11-14 15:45:22 UTC
Note: I tried cherry-picking it into 5.2, but that gave a merge conflict. Not sure how to proceed, so I'm not doing anything about it now, but if having this fix in 5.2 would be important, I can look into it.