Remove sentinels as they race with multi threading #217

niklas88 · 2019-03-27T14:12:42Z

Also add some TODOs for ideas how to get joins faster and we may still remove the gotos

joka921 · 2019-03-28T08:26:13Z

src/engine/Engine.h

        }
+
        while (a(i, jc1) == b(j, jc2)) {
          // In case of match, create cross-product


If I am not mistaken, the inner while loop that handles the cross-product is always the same
for all join-related functions. With inlining etc. I should not cost performance, and if we can measure.

The only problem with this is that it manipulates i and j and thus we would either have to pass them as size_t* or have it return e.g. a std::pair<size_t, size_t> and kind of awkwardly update i and j with that. Sadly one can't assign in a structured binding.

Speaking of killing code duplication, I think we should try to merge the two galloping cases. I'll give it a try

joka921

Idea: We could handle the sentinels inside the IdTable
by using a finalizeSentinels class, that writes a maximums beyond bounds. Afterwards we have the sentinel in the off-by-one area and can use them with the old code.

joka921 · 2019-03-28T10:58:04Z

src/engine/Engine.h

      if (l2(j, jc2) > l1(i, jc1)) {
-        Id* val = new Id[l1.cols()];
        val[jc1] = l2(j, jc2);
        i = std::lower_bound(l1.begin() + i, l1.end(), val,
                             [jc1](const auto& l, const auto& r) -> bool {
                               return l[jc1] < r[jc1];
                             }) -


I have an even better idea:

Id val = l2(j, jc2); i = std::lower_bound(l1.begin() + i, l1.end(), val, [jc1](const auto& l, const auto& r) -> bool { return l[jc1] < r; }) -

No new

no constexpr

always efficient and sufficient.

Good catch. I've included this and also tried (see other comment) that this isn't what made the non-sentinel version faster.

niklas88 · 2019-03-28T13:09:58Z

Idea: We could handle the sentinels inside the IdTable
by using a finalizeSentinels class, that writes a maximums beyond bounds. Afterwards we have the sentinel in the off-by-one area and can use them with the old code.

Let's first see how much performance the removal of sentinels costs us. I think while the code looks cleaner they are also harder to reason about so they really need to pay for themselves with performance

niklas88 · 2019-03-28T13:43:32Z

@joka921 ok this is interesting. Turns out, this branch is actually 22% faster than current master and still 18% faster than the master branch after applying your change to the use of std::lower_bound

With sentinels and new/delete:

Average completion moves: 4.52 (vs 8.51 manually)
Executed 272 queries in 15032.706 seconds
with the following timings

Average: 55.27 ms/query
Max: 837.45 ms/query
90th percentile: 106.33 ms/query
70th percentile: 71.68 ms/query
50th percentile: 8.52 ms/query

With sentinels but no new/delete:

Average completion moves: 4.52 (vs 8.51 manually)
Executed 272 queries in 14579.671 seconds
with the following timings

Average: 53.60 ms/query
Max: 833.57 ms/query
90th percentile: 109.39 ms/query
70th percentile: 70.67 ms/query
50th percentile: 7.94 ms/query

Without sentinels:

Average completion moves: 4.52 (vs 8.51 manually)
Executed 287 queries in 13004.729 seconds
with the following timings

Average: 45.31 ms/query
Max: 710.91 ms/query
90th percentile: 93.13 ms/query
70th percentile: 27.60 ms/query
50th percentile: 5.30 ms/query

So it looks like sentinels are actually bad for performance. I guess without them the compiler just knows more and the branch predictor has no problems guessing the branches that one safes anyway.

niklas88 · 2019-03-28T15:23:51Z

216 fewer lines of code to break with all the same features but ~22% faster. Inflationary…

niklas88 · 2019-03-28T17:06:21Z

I've found another broken use of sentinels in the Text stuff. Will have to fix that tomorrow as the straightforward versions doesn't seem to work yet

joka921 · 2019-03-28T17:54:54Z

src/index/Index.cpp

@@ -1312,7 +1312,6 @@ void Index::scanOSP(const string& object, IdTable* result) const {
 void Index::scanPSO(Id predicate, IdTable* result) const {


Nice finding, but you probably will run into trouble after my reworking of the index class.
Maybe cancel this change, then rebase, then add it again:)

Also add some TODOs for ideas how to get joins faster

Also without the delete we can just return

I decided to test this with valgrind and found an error in join() but also some in Simpl8bCode, Filter and the Server.

joka921

LGTM,
I have one suggestion and 2-3 questions for clarification.

joka921 · 2019-03-29T17:02:50Z

src/engine/OptionalJoin.cpp

@@ -472,28 +459,20 @@ void OptionalJoin::optionalJoin(const IdTable& dynA, const IdTable& dynB,
      }
    }
  }
-


In the code above you could also replace ==x.size() by >=x.size to be consistent.

joka921 · 2019-03-29T17:05:23Z

src/engine/Server.cpp

+    _serverSocket.close();
+  }
+}
+


Probably never a problem if the Server is the only thing running in a problem but nevertheless always important to clean up open network stuff.

joka921 · 2019-03-29T17:27:24Z

src/util/Simple8bCode.h

+      ++nofCodeWordsDone;
+      if (nofElementsDone < nofElements) {
+        selector = encoded[nofCodeWordsDone] & SIMPLE8B_SELECTOR_MASK;
+      }


Nice refactoring!
Just to my understanding:

The loops are almost equivalent, yours is just better readable.

The original code had an off-by-one error (selector = encoded[nofCodeWordsDone] & SIMPLE8B_SELECTOR_MASK; was also executed one last time but never used.

Yes, that's how I understand it as well

joka921 · 2019-03-29T17:28:45Z

src/util/Socket.h

-    return ::bind(_fd, res->ai_addr, res->ai_addrlen) != -1;
+    bool success = ::bind(_fd, res->ai_addr, res->ai_addrlen) != -1;
+    freeaddrinfo(res);
+    return success;


I don't understand enough of manual socket programming to properly review this line.

joka921 reviewed Mar 28, 2019

View reviewed changes

niklas88 mentioned this pull request Mar 29, 2019

First try of using parallelism in the sort operation #216

Closed

niklas88 added 11 commits March 29, 2019 10:09

Remove sentinels as they race with multi threading

6f319fa

Also add some TODOs for ideas how to get joins faster

Implement Johannes suggestion to eliminate alloc

8176666

Also without the delete we can just return

Tighten inner loop, remove now-unneeded doSelfJoin

1a9eaa9

Remove unused Engine methods

8057ccc

A few simplifications and a new galloping TODO

dfad905

Compile time switch larger/smaller in doGallopJoin

7cb214d

Remove now-unneeded reserves for sentinels

4b681b2

Remove sentinels in FTSAlgorithms intersects

a6b4775

Remove sentinels in MultiColumn and OptionalJoin

c586f88

Fix Valgrind errors

554f9ab

I decided to test this with valgrind and found an error in join() but also some in Simpl8bCode, Filter and the Server.

Simple8bCode: Also handle empty decode

d12acfd

niklas88 requested a review from joka921 March 29, 2019 16:12

joka921 approved these changes Mar 29, 2019

View reviewed changes

Johannes' suggestions

24dadbd

niklas88 merged commit 08047fa into ad-freiburg:master Mar 29, 2019

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Remove sentinels as they race with multi threading #217

Remove sentinels as they race with multi threading #217

niklas88 commented Mar 27, 2019

joka921 Mar 28, 2019

niklas88 Mar 28, 2019

niklas88 Mar 28, 2019

joka921 left a comment

joka921 Mar 28, 2019

niklas88 Mar 28, 2019

niklas88 commented Mar 28, 2019

niklas88 commented Mar 28, 2019 •

edited

niklas88 commented Mar 28, 2019

niklas88 commented Mar 28, 2019

joka921 Mar 28, 2019

joka921 left a comment

joka921 Mar 29, 2019

joka921 Mar 29, 2019

joka921 Mar 29, 2019

niklas88 Mar 29, 2019

joka921 Mar 29, 2019

		@@ -1312,7 +1312,6 @@ void Index::scanOSP(const string& object, IdTable* result) const {
		void Index::scanPSO(Id predicate, IdTable* result) const {

Remove sentinels as they race with multi threading #217

Remove sentinels as they race with multi threading #217

Conversation

niklas88 commented Mar 27, 2019

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

joka921 left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

niklas88 commented Mar 28, 2019

niklas88 commented Mar 28, 2019 • edited

niklas88 commented Mar 28, 2019

niklas88 commented Mar 28, 2019

Choose a reason for hiding this comment

joka921 left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

niklas88 commented Mar 28, 2019 •

edited