From 75e9858a87307f61b478735f73c0a60c52c25eb8 Mon Sep 17 00:00:00 2001 From: Viktor Engelmann Date: Thu, 21 Dec 2017 16:11:54 +0100 Subject: Significantly improve memory usage in XsdStateMachine::toDFA We now mark DFA state sets immediately when they are enqueued and check for that mark before enqueing them. This way, we save a lot of memory when a set has many states and is encountered often. In the referenced bug report, there were 60000 copies of a set with 40000 entries, wasting tens of gigabytes of memory. Task-number: QTBUG-65067 Change-Id: Iec3a04c8badfac29faefbba22c2942ed104effbb Reviewed-by: Kari Hormi Reviewed-by: Erik Verbruggen --- src/xmlpatterns/schema/qxsdstatemachine_tpl_p.h | 16 +++++++--------- 1 file changed, 7 insertions(+), 9 deletions(-) diff --git a/src/xmlpatterns/schema/qxsdstatemachine_tpl_p.h b/src/xmlpatterns/schema/qxsdstatemachine_tpl_p.h index 1cb2e72..9277c1b 100644 --- a/src/xmlpatterns/schema/qxsdstatemachine_tpl_p.h +++ b/src/xmlpatterns/schema/qxsdstatemachine_tpl_p.h @@ -359,19 +359,14 @@ XsdStateMachine XsdStateMachine::toDFA() const QList< QSet > workStates; // add the start state to the list of to processed state sets - workStates.append(epsilonClosure(QSet() << startState)); + auto firstDfaState = epsilonClosure(QSet() << startState); + workStates.append(firstDfaState); + isMarked.append(firstDfaState); while (!workStates.isEmpty()) { // as long as there are state sets to process left - // enqueue set of states const QSet states = workStates.takeFirst(); - if (isMarked.contains(states)) // we processed this state set already - continue; - - // mark as processed - isMarked.append(states); - // select a list of all inputs that are possible for // the 'states' set QList input; @@ -395,7 +390,10 @@ XsdStateMachine XsdStateMachine::toDFA() const dfa.addTransition(dfaBegin, input.at(i), dfaEnd); // add the 'followStates' to the list of to be processed state sets - workStates.append(followStates); + if (!isMarked.contains(followStates)) { + workStates.append(followStates); + isMarked.append(followStates); // only needs to be processed once + } } } -- cgit v1.2.1