Refactoring #2410

Core: beam propagation: Speeding up computations on samples with a large number of layers

Added by dmitry 11 months ago. Updated 9 days ago.

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

0%

Category:-
Target version:-

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 Rejected 30 Apr 2019
Related to BornAgain - Feature #2336: Make reflectometry computation as fast as in Refnx Resolved 04 Apr 2019

History

#1 Updated by dmitry 10 months ago

#2 Updated by dmitry 10 months ago

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

#3 Updated by pospelov 6 months ago

  • Target version deleted (v2.0)

#4 Updated by pospelov 6 months ago

  • Status changed from Backlog to Sprint
  • Target version set to Sprint 43

#5 Updated by pospelov 3 months ago

  • Status changed from Sprint to Backlog
  • Target version deleted (Sprint 43)

#6 Updated by wuttke 9 days ago

  • Subject changed from Speeding up computations on samples with a large number of layers to Core: beam propagation: Speeding up computations on samples with a large number of layers

#7 Updated by wuttke 9 days ago

  • Assignee set to rbeerwerth

Randolf: May be you should reinvestigate this in connection with your current work on beam propagation.

Also available in: Atom PDF