Refactoring #2410

Speeding up computations on samples with a large number of layers

Added by dmitry about 2 months ago.

Status:BacklogStart date:21 Oct 2019
Priority:NormalDue date:
Assignee:-% Done:

0%

Category:-
Target version:v2.0

Description

Despite recent speed up in computations on a large number of layers,
the computation complexity is still O(N^2), where N is the number of layers in the sample.
The computation engine is capable of working with worst-case complexity of O(N logN).

The reason for such slow computations is in INode::createParameterTree():

1. To build string paths it computes the number of copies of same-type objects in the sample.
Each of the uniform objects requires the counting of its siblings, total complexity of the computation
being O(N^2). This problem can be solved as in pull-request 881,
providing 1.5 times speed-up on 1000 layer-thick sample.

2. Second problem is the string concatenation and reallocation: if optimized, it can provide another factor of 2 speed-up on 1000 layers.
One can find a screenshot of kcachegrind output in the same PR.

To measure the performance, one can use the dedicated performance test in Tests/Functional/Core/CoreSpecial/MultilayerPerformanceTest.(h,cpp)


Related issues

Related to BornAgain - Refactoring #2343: Improve performance in reflectometry engine Backlog 30 Apr 2019
Related to BornAgain - Feature #2336: Make reflectometry computation as fast as in Refnx Backlog 04 Apr 2019

History

#1 Updated by dmitry 17 days ago

#2 Updated by dmitry 17 days ago

  • Related to Feature #2336: Make reflectometry computation as fast as in Refnx added

Also available in: Atom PDF