Ticket #9497 (closed Bug: fixed)
PortalTransforms scalability problems (performance improvement, a patch for _findPath)
|Reported by:||sig||Owned by:||hannosch|
|Keywords:||archetypes, portaltransforms, _findPath, _getPaths, scalability, performance, optimization||Cc:|
Products.PortalTransforms.TransformEngine has a terrible _findPath method in terms of performance and scalability (especially against the number of mimetypes supported by transforms). For instance, if you have an image transformer which supports, let's say, 15 mimetypes in input and outputs, then the current naive algorithm will do about 15! (factorial 15 = 1.307.674.368.000) loops.
Here is a discussion thread mentioning the horror in _findPath/_getPaths : http://plone.org/support/forums/general#nabble-td310736
Here is a patch which proposes 2 levels of optimization :
1) simple optimization heuristics (early path pruning) in _getPaths (changes the semantic of _getPaths a bit but this shouldn't matter)
2) a better shortest-path finding algorithm in _findPath (which, BTW, does not call _getPaths any more and _getPaths might then be removed)
If ever you don't want to deal with the proposed path-finding algorithm, please note that you may ignore this second level of optimization (changes in _findPath) and just commit the first one (changes in _getPaths). The improvement in scalability and performance will already be significant.
What do you think?
- Owner changed from nouri to hannosch
- Status changed from new to assigned
- Status changed from assigned to closed
- Resolution set to fixed
- Status changed from closed to reopened
- Resolution fixed deleted