Skip to content

Eradicate the IdList bottleneck #992

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.

Sign up for GitHub

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

Closed
pjanx wants to merge 6 commits into from
Closed

Eradicate the IdList bottleneck #992

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
6 commits
Select commit Hold shift + click to select a range
5f0d25c
GTK: silence a compiler warning
pjanx Apr 3, 2021
e2fb147
IdList speedup 1: maintain an array of indexes
pjanx Apr 3, 2021
0e3fba0
IdList speedup 2: use iterators
pjanx Apr 3, 2021
a3d4359
IdList speedup 3: optimize allocations
pjanx Apr 3, 2021
6c55182
IdList speedup 4: make RemoveTagged fast again
pjanx Apr 4, 2021
3b395bb
IdList speedup 5: use range for rather than NextAfter
pjanx Apr 3, 2021
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
19 changes: 9 additions & 10 deletions src/clipboard.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -138,18 +138,17 @@ void GraphicsWindow::CopySelection() {
}
}

Constraint *c;
for(c = SK.constraint.First(); c; c = SK.constraint.NextAfter(c)) {
if(!SS.clipboard.ContainsEntity(c->ptA) ||
!SS.clipboard.ContainsEntity(c->ptB) ||
!SS.clipboard.ContainsEntity(c->entityA) ||
!SS.clipboard.ContainsEntity(c->entityB) ||
!SS.clipboard.ContainsEntity(c->entityC) ||
!SS.clipboard.ContainsEntity(c->entityD) ||
c->type == Constraint::Type::COMMENT) {
for(Constraint &c : SK.constraint) {
if(!SS.clipboard.ContainsEntity(c.ptA) ||
!SS.clipboard.ContainsEntity(c.ptB) ||
!SS.clipboard.ContainsEntity(c.entityA) ||
!SS.clipboard.ContainsEntity(c.entityB) ||
!SS.clipboard.ContainsEntity(c.entityC) ||
!SS.clipboard.ContainsEntity(c.entityD) ||
c.type == Constraint::Type::COMMENT) {
continue;
}
SS.clipboard.c.Add(c);
SS.clipboard.c.Add(&c);
}
}

Expand Down
17 changes: 8 additions & 9 deletions src/draw.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -210,16 +210,15 @@ void GraphicsWindow::SelectByMarquee() {
BBox marqueeBBox = BBox::From(Vector::From(marqueePoint.x, marqueePoint.y, VERY_NEGATIVE),
Vector::From(orig.mouse.x, orig.mouse.y, VERY_POSITIVE));

Entity *e;
for(e = SK.entity.First(); e; e = SK.entity.NextAfter(e)) {
if(e->group != SS.GW.activeGroup) continue;
if(e->IsFace() || e->IsDistance()) continue;
if(!e->IsVisible()) continue;
for(Entity &e : SK.entity) {
if(e.group != SS.GW.activeGroup) continue;
if(e.IsFace() || e.IsDistance()) continue;
if(!e.IsVisible()) continue;

bool entityHasBBox;
BBox entityBBox = e->GetOrGenerateScreenBBox(&entityHasBBox);
BBox entityBBox = e.GetOrGenerateScreenBBox(&entityHasBBox);
if(entityHasBBox && entityBBox.Overlaps(marqueeBBox)) {
MakeSelected(e->h);
MakeSelected(e.h);
}
}
}
Expand Down Expand Up @@ -412,8 +411,8 @@ void GraphicsWindow::HitTestMakeSelection(Point2d mp) {
cached.projRight = projRight;
cached.projUp = projUp;
cached.scale = scale;
for(Entity *e = SK.entity.First(); e; e = SK.entity.NextAfter(e)) {
e->screenBBoxValid = false;
for(Entity &e : SK.entity) {
e.screenBBoxValid = false;
}
}

Expand Down
165 changes: 82 additions & 83 deletions src/dsc.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -388,12 +388,36 @@ struct CompareId {
template <class T, class H>
class IdList {
T *elem = nullptr;
int *indexes = nullptr;
int elemsAllocated = 0;
public:
int n = 0;

using Compare = CompareId<T, H>;

struct Iterator {
typedef std::random_access_iterator_tag iterator_category;
typedef T value_type;
typedef int difference_type;
typedef T *pointer;
typedef T &reference;

IdList<T, H> *list;
int offset;

Iterator(IdList<T, H> &list, int offset) : list(&list), offset(offset) {}
T &operator*() { return list->elem[list->indexes[offset]]; }
Copy link
Copy Markdown
Member

@ruevs ruevs Apr 4, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

On mine I kept a local T *elem updated when the iterator is changed so that * and -> can be fast. They may be called many times per loop iteration, and ++ usually only once.

Copy link
Copy Markdown
Contributor Author

@pjanx pjanx Apr 4, 2021 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

That's one thing optimizers should be good at, unless some aliasing rules break it. I'd be somewhat surprised if it'd be measurable for the added complexity. Making offset point directly into the indexes array is more obvious. And both of these suffer if the array is resized during iteration, which STL just declares as undefined behaviour in such situations.

T *operator->() { return &list->elem[list->indexes[offset]]; }
const T &operator*() const { return list->elem[list->indexes[offset]]; }
Copy link
Copy Markdown
Member

@ruevs ruevs Apr 4, 2021 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

We should carefully review the need for const methods and in which of the former NextAfter loops we can add const. Luckily this is just a lot of clicking and testing if the compiler will agree ;-)

What do you think - should we remove the unused overloads in the end? I'm split between having a short iterator and a "complete" one with mostly unused methods. @phkahler ? @rpavlik ?

Copy link
Copy Markdown
Contributor Author

@pjanx pjanx Apr 4, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

MSVC required me to add const versions here, for std::lower_bound. See the first comment of the PR.

Copy link
Copy Markdown
Contributor

@rpavlik rpavlik Apr 5, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'm inclined to think just implement the code that's needed on the YAGNI principle. Unused methods are untested and possible traps for the future.

Copy link
Copy Markdown
Member

@ruevs ruevs Apr 7, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Removed all unused methods from mine.

const T *operator->() const { return &list->elem[list->indexes[offset]]; }
Iterator &operator--() { --offset; return *this; }
Iterator &operator++() { ++offset; return *this; }
Iterator &operator+=(int diff) { offset += diff; return *this; }
int operator-(const Iterator &i) const { return offset - i.offset; }
bool operator==(const Iterator &i) { return list == i.list && offset == i.offset; }
Copy link
Copy Markdown
Member

@ruevs ruevs Apr 4, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I should fix this - I'm not comparing the lists for equality after I removed the bounds checking in my last commit ruevs@6bc1aa9

Copy link
Copy Markdown
Contributor Author

@pjanx pjanx Apr 4, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It should rather be an assertion rather than a direct test like this.

Copy link
Copy Markdown
Member

@ruevs ruevs Apr 4, 2021 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It was an assertion before I removed it ;-) Maybe I'll put them back in.

bool operator!=(const Iterator &i) { return list != i.list || offset != i.offset; }
};

bool IsEmpty() const {
return n == 0;
}
Expand All @@ -408,7 +432,7 @@ class IdList {
if(IsEmpty()) {
return 0;
} else {
return Last()->h.v;
return elem[indexes[n-1]].h.v;
}
}

Expand All @@ -417,46 +441,38 @@ class IdList {
AllocForOneMore();

// Copy-construct at the end of the list.
indexes[n] = n;
new(&elem[n]) T(*t);
++n;

return t->h;
}

T * LowerBound(T const& t) {
if(IsEmpty()) {
return nullptr;
}
auto it = std::lower_bound(begin(), end(), t, Compare());
return it;
Iterator LowerBound(T const& t) {
return std::lower_bound(begin(), end(), t, Compare());
}

T * LowerBound(H const& h) {
if(IsEmpty()) {
return nullptr;
}
auto it = std::lower_bound(begin(), end(), h, Compare());
return it;
Iterator LowerBound(H const& h) {
return std::lower_bound(begin(), end(), h, Compare());
Copy link
Copy Markdown
Member

@ruevs ruevs Apr 4, 2021 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I opted to use iterators on the index and complicated the predicate on the theory that the vector<int> iterator is simpler than my IdList one and thus hoping it would be faster. But I have not profiled to confirm.

Copy link
Copy Markdown
Contributor Author

@pjanx pjanx Apr 4, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I wouldn't expect a meaningful difference, it boils down to a few pointer operations. Didn't you have to add a forward declaration and complicate CompareId because of that?

Copy link
Copy Markdown
Member

@ruevs ruevs Apr 5, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yes. I called `CompareId" the predicate.

}

int LowerBoundIndex(T const& t) {
if(IsEmpty()) {
return 0;
}
auto it = LowerBound(t);
auto idx = std::distance(begin(), it);
auto i = static_cast<int>(idx);
return i;
return std::distance(begin(), LowerBound(t));
}

void ReserveMore(int howMuch) {
if(n + howMuch > elemsAllocated) {
elemsAllocated = n + howMuch;
int *newIndexes = (int *)::operator new[]((size_t)elemsAllocated*sizeof(int));
Copy link
Copy Markdown
Member

@ruevs ruevs Apr 4, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Using vector for the storage gets rid of the manual memory management, and hopefully at least in release mode should be as fast.

Copy link
Copy Markdown
Contributor Author

@pjanx pjanx Apr 4, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

That's one of the things that should be unified throughout the codebase, I'm just using what's already there.

I don't even know how the custom allocator library is hooked up.

@Evil-Spirit wanted to use realloc, which should be a trick that std::vector could be able to do as well, though I'm dubious whether it's useful for geometric steps.

Copy link
Copy Markdown
Contributor

@rpavlik rpavlik Apr 5, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The important bit is that idlist is reference semantics, not value semantics, so you can't embed a std::vector, but rather a std::shared_ptrstd::vector - a lesson I learned painfully.

Copy link
Copy Markdown
Member

@ruevs ruevs Apr 7, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@rpavlik Do you mean to say that once a pointer to an element is "taken out' of an IdList it may be kept around and dereferenced after the list has been modified? And thus the pointer may be invalid?

If this is the case can you point to an example?

But this does not make sense - the original implementation of IdList did not guarantee that the elemnts will not move - in fact it moved them around all the time!

In fact my implementation is "better" in this respect since it never moves elements once they are added because the elemstore is not rearranged when elements are removed:
https://github.com/ruevs/solvespace/blob/3c6e2be4b920d706d8231030467c5271a6d87d85/src/dsc.h#L570
the removed elements are simply added to the freelist.

T *newElem = (T *)::operator new[]((size_t)elemsAllocated*sizeof(T));
memcpy(newIndexes, indexes, sizeof *newIndexes * n);
for(int i = 0; i < n; i++) {
new(&newElem[i]) T(std::move(elem[i]));
elem[i].~T();
}
::operator delete[](indexes);
::operator delete[](elem);
indexes = newIndexes;
elem = newElem;
}
}
Expand All @@ -467,16 +483,13 @@ class IdList {
// Look to see if we already have something with the same handle value.
ssassert(FindByIdNoOops(t->h) == nullptr, "Handle isn't unique");

// Find out where the added element should be.
// Shift indexes to the end of the array, if needed.
int pos = LowerBoundIndex(*t);
memmove(indexes + pos + 1, indexes + pos, sizeof *indexes * (n - pos));
Copy link
Copy Markdown
Member

@ruevs ruevs Apr 4, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I wonder if insert in a vector<int> is as fast. I'll debug it tomorrow to see what it does.

Copy link
Copy Markdown
Contributor Author

@pjanx pjanx Apr 4, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It should optimize that way.


// Shift everything from there to the end of the array.
new(&elem[n]) T();
for (int i = n; i > pos; i--)
elem[i] = std::move(elem[i - 1]);

// Copy-construct at the right place.
elem[pos] = T(*t);
// Copy-construct at the end of the list.
indexes[pos] = n;
new(&elem[n]) T(*t);
++n;
}

Expand All @@ -486,55 +499,21 @@ class IdList {
return t;
}

int IndexOf(H h) {
if(IsEmpty()) {
return -1;
}
auto it = LowerBound(h);
auto idx = std::distance(begin(), it);
if (idx < n) {
return idx;
}
return -1;
}

T *FindByIdNoOops(H h) {
if(IsEmpty()) {
return nullptr;
}
auto it = LowerBound(h);
if (it == nullptr || it == end()) {
return nullptr;
}
if (it->h.v == h.v) {
return it;
if(it != end() && it->h.v == h.v) {
return &*it;
}
return nullptr;
}

T *First() {
return (IsEmpty()) ? NULL : &(elem[0]);
}
T *Last() {
return (IsEmpty()) ? NULL : &(elem[n-1]);
}
T *NextAfter(T *prev) {
if(IsEmpty() || !prev) return NULL;
if(prev - First() == (n - 1)) return NULL;
return prev + 1;
}

T &Get(size_t i) { return elem[i]; }
T const &Get(size_t i) const { return elem[i]; }
T &Get(size_t i) { return elem[indexes[i]]; }
T const &Get(size_t i) const { return elem[indexes[i]]; }
T &operator[](size_t i) { return Get(i); }
T const &operator[](size_t i) const { return Get(i); }

T *begin() { return IsEmpty() ? nullptr : &elem[0]; }
T *end() { return IsEmpty() ? nullptr : &elem[0] + n; }
const T *begin() const { return IsEmpty() ? nullptr : &elem[0]; }
Copy link
Copy Markdown
Member

@ruevs ruevs Apr 4, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

As above - the const iterators may be useful for compiler optimisations, if we can add const in some places where IdLists are used.

Copy link
Copy Markdown
Contributor Author

@pjanx pjanx Apr 4, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'd be interested in seeing evidence of any difference in this case.

const T *end() const { return IsEmpty() ? nullptr : &elem[0] + n; }
const T *cbegin() const { return begin(); }
const T *cend() const { return end(); }
Iterator begin() { return Iterator(*this, 0); }
Iterator end() { return Iterator(*this, n); }

void ClearTags() {
for(auto &elt : *this) { elt.tag = 0; }
Expand All @@ -548,23 +527,38 @@ class IdList {
}

void RemoveTagged() {
int src, dest;
dest = 0;
for(src = 0; src < n; src++) {
if(elem[src].tag) {
// this item should be deleted
elem[src].Clear();
} else {
if(src != dest) {
elem[dest] = elem[src];
}
dest++;
std::vector<int> elem2indexes(n);
Copy link
Copy Markdown
Member

@ruevs ruevs Apr 4, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I need to trace through this with the debugger to really get it. Tomorrow.

for(int i = 0; i < n; i++) {
elem2indexes[indexes[i]] = i;
}

int newN = n;
for(int i = 0; i < newN; ) {
if(!elem[i].tag) {
i++;
continue;
}

// This item should be deleted.
elem[i].Clear();
indexes[elem2indexes[i]] = -1;

// If we've made a gap in the elem array, fill it up.
if(i < --newN) {
elem[i] = std::move(elem[newN]);
elem2indexes[i] = elem2indexes[newN];
indexes[elem2indexes[newN]] = i;
}

elem[newN].~T();
}

// Remove tombstones transferred from tags.
// elemsAllocated is untouched, because we didn't resize.
if(newN != n) {
std::remove(indexes, indexes + n, -1);
n = newN;
}
for(int i = dest; i < n; i++)
elem[i].~T();
n = dest;
// and elemsAllocated is untouched, because we didn't resize
}
void RemoveById(H h) {
ClearTags();
Expand All @@ -575,13 +569,16 @@ class IdList {
void MoveSelfInto(IdList<T,H> *l) {
l->Clear();
std::swap(l->elem, elem);
std::swap(l->indexes, indexes);
std::swap(l->elemsAllocated, elemsAllocated);
std::swap(l->n, n);
}

void DeepCopyInto(IdList<T,H> *l) {
l->Clear();
l->indexes = (int *)::operator new[](elemsAllocated * sizeof(indexes[0]));
l->elem = (T *)::operator new[](elemsAllocated * sizeof(elem[0]));
memcpy(l->indexes, indexes, elemsAllocated * sizeof(indexes[0]));
for(int i = 0; i < n; i++)
new(&l->elem[i]) T(elem[i]);
l->elemsAllocated = elemsAllocated;
Expand All @@ -593,7 +590,9 @@ class IdList {
elem[i].Clear();
elem[i].~T();
}
if(indexes) ::operator delete[](indexes);
if(elem) ::operator delete[](elem);
indexes = NULL;
elem = NULL;
elemsAllocated = n = 0;
}
Expand Down
11 changes: 5 additions & 6 deletions src/exportstep.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -353,22 +353,21 @@ void StepFileWriter::ExportSurfacesTo(const Platform::Path &filename) {

advancedFaces = {};

SSurface *ss;
for(ss = shell->surface.First(); ss; ss = shell->surface.NextAfter(ss)) {
if(ss->trim.IsEmpty())
for(SSurface &ss : shell->surface) {
if(ss.trim.IsEmpty())
continue;

// Get all of the loops of Beziers that trim our surface (with each
// Bezier split so that we use the section as t goes from 0 to 1), and
// the piecewise linearization of those loops in xyz space.
SBezierList sbl = {};
ss->MakeSectionEdgesInto(shell, NULL, &sbl);
ss.MakeSectionEdgesInto(shell, NULL, &sbl);

// Apply the export scale factor.
ss->ScaleSelfBy(1.0/SS.exportScale);
ss.ScaleSelfBy(1.0/SS.exportScale);
sbl.ScaleSelfBy(1.0/SS.exportScale);

ExportSurface(ss, &sbl);
ExportSurface(&ss, &sbl);

sbl.Clear();
}
Expand Down
Loading