AutoPas / AutoPas/AutoPas

Inefficient Octree Update

Open
#622 1 comment 0 reactions 0 assignees View on GitHub
enhancement optimization
Dominant language
C++
Stars
52
Forks
17
PR merge metrics
No merged PRs in 30d

Description

**Description**

Currently, the `updateContainer` method of the octree behaves as follows:

1. Copy all particles out of the container
2. Clear the container
3. Insert the particles back into the container

The runtime complexity of copying particles out of and back into an octree is _O(n)_, this is not a very costly operation compared to for instance `traverseParticlePairs`. The problem is that the operation does a _lot of copying memory_ for no reason, which may require optimization.

**Solution**

- [ ] Evaluate whether the memory and speed penalties implicated by this approach actually matter in practice.
- [ ] Find better ways to update an octree (for instance put all particles in their respective leaf and then re-balance the entire tree by looking at inner nodes and checking whether they can be collapsed into a single leaf)

**Context**

The issue refers to the octree implementation in #610.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.