Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Lighten memory footprint for each segment #31

Closed
mfogel opened this issue Aug 5, 2018 · 1 comment
Closed

Lighten memory footprint for each segment #31

mfogel opened this issue Aug 5, 2018 · 1 comment
Labels
performance Possible performance improvement
Milestone

Comments

@mfogel
Copy link
Owner

mfogel commented Aug 5, 2018

Right now, each segment has the following structure:

class Segment {
  coincidents = [this, ...]  // list of segments that *exactly* overlap this segment, including itself
  ringIn = <ring>            // the input ring this segment came from
  flowL2R = <boolean>        // the direction, clockwise or counter-clockwise, this segment faced in its input ring
  ...
}

This is somewhat wasteful because nearly all input segments have only one coincident - themselves. So Segment.coincidents is nearly always just a one-element array. So one possible performance improvement would be to leave Segment.coincidents undefined until at least one coincident segment is identified, and at that point initialize it to an array of two segments: [this, otherSeg].

Even better would be:

First, by addressing #30, hopefully the need to carry around the boolean flowL2R goes away.

Then the following structure would be possible:

class Segment {
    ringsIn = [<ring>, ...] // list of input rings this segment represents
    ...
}

This drops the coincidents array altogether. Essentially when two segments realize they're coincident, instead of just marking themselves as such, one would 'die' and give its input ringIn to the surviving segment. The dieing segment could either be marked 'dead' with a tombstone or it could be proactively removed from the datastructures (the sorted tree of segments and the sweep event priority queue).

And from here, since 99% of input segments only represent one ring, we could employe the the following more complicated, but likely more performant structure:

class Segment {
  ringIn = <ring>                    // only defined when the segment represents just one ring
  ringsIn = [<ring1>, <ring2>, ... ] // only defined when the segment represents two or more rings
  ...
}
@mfogel mfogel added the performance Possible performance improvement label Aug 5, 2018
@mfogel mfogel closed this as completed in e98aff6 Nov 22, 2018
@mfogel
Copy link
Owner Author

mfogel commented Nov 22, 2018

Breaking up the segment.ringsIn array into two parts (segment.ringIn and segment.ringsIn) did not end up yielding noticeable performance gains in the benchmark, and complicated the code appreciably, as such that was not implemented.

However, the segment.coincidents array has been dropped as suggested in this ticket and replaced with the simpler and more performant segment.ringsIn array.

@mfogel mfogel added this to the v0.10 milestone Jan 7, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
performance Possible performance improvement
Projects
None yet
Development

No branches or pull requests

1 participant