summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorViktor Engelmann <viktor.engelmann@qt.io>2017-12-21 15:11:54 (GMT)
committerViktor Engelmann <viktor.engelmann@qt.io>2018-01-04 11:21:27 (GMT)
commit75e9858a87307f61b478735f73c0a60c52c25eb8 (patch)
tree2f45bae9669f37c17317e1f28a57a36be26f7473
parent4e2f2f60c2b40e462be2d75cd81f149522097734 (diff)
downloadqtxmlpatterns-75e9858a87307f61b478735f73c0a60c52c25eb8.tar.gz
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 <kari.hormi@qt.io> Reviewed-by: Erik Verbruggen <erik.verbruggen@qt.io>
-rw-r--r--src/xmlpatterns/schema/qxsdstatemachine_tpl_p.h16
1 files 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<TransitionType> XsdStateMachine<TransitionType>::toDFA() const
QList< QSet<StateId> > workStates;
// add the start state to the list of to processed state sets
- workStates.append(epsilonClosure(QSet<StateId>() << startState));
+ auto firstDfaState = epsilonClosure(QSet<StateId>() << 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<StateId> 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<TransitionType> input;
@@ -395,7 +390,10 @@ XsdStateMachine<TransitionType> XsdStateMachine<TransitionType>::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
+ }
}
}