You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@trafficserver.apache.org by AZNova <gi...@git.apache.org> on 2015/08/31 19:45:16 UTC
[GitHub] trafficserver pull request: TS 3867 - Improved qsort
GitHub user AZNova opened a pull request:
https://github.com/apache/trafficserver/pull/286
TS 3867 - Improved qsort
Updated qsort algo to a median of 3 qsort.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/AZNova/trafficserver TS-3867
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/trafficserver/pull/286.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #286
----
commit 0041dee9df726fe401fb3e6dff1ea835fefda688
Author: Steven Feltner <sf...@godaddy.com>
Date: 2015-08-31T16:05:02Z
TS-3867 - qsort updated to a median of 3 qsort.
commit 645d57f8e76551e75a5dcab1ff71425093930160
Author: Steven Feltner <sf...@godaddy.com>
Date: 2015-08-31T17:38:11Z
TS-3867 - qsort updated to a median of 3 qsort.
----
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] trafficserver pull request: TS 3867 - Improved qsort
Posted by jpeach <gi...@git.apache.org>.
Github user jpeach commented on the pull request:
https://github.com/apache/trafficserver/pull/286#issuecomment-136489609
I ran the regression tests on OS X with this patch, and saw some [memory leaks](http://apaste.info/z1O). the ```test_certlookup``` test (part of ```make check```) shows these.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] trafficserver pull request: TS 3867 - Improved qsort
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit closed the pull request at:
https://github.com/apache/trafficserver/pull/286
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] trafficserver pull request: TS 3867 - Improved qsort
Posted by SolidWallOfCode <gi...@git.apache.org>.
Github user SolidWallOfCode commented on a diff in the pull request:
https://github.com/apache/trafficserver/pull/286#discussion_r38672458
--- Diff: lib/ts/Vec.h ---
@@ -964,41 +965,71 @@ qsort_Vec(C *left, C *right, bool (*lt)(C, C))
}
}
} else {
- C *i = left + 1, *j = right - 1;
- C x = *left;
- for (;;) {
- while (lt(x, *j))
- j--;
- while (i < j && lt(*i, x))
- i++;
- if (i >= j)
- break;
- C t = *i;
- *i = *j;
- *j = t;
- i++;
- j--;
+ C *center = left + ((right - left) / 2);
+ C median;
+
+ // find the median
+ if (lt(*center, *left)){ // order left and center
+ swap(center, left);
+ }
+ if (lt(*(right-1), *left)){ // order left and right
+ swap(right-1, left);
+ }
+ if (lt(*(right-1), *center)){ // order right and center
+ swap((right-1), center);
+ }
+ swap(center, right-2); // stash the median one from the right for now
+ median = *(right-2); // and that's the median of the 3
+
+ // now partition, pivoting on the median value
+ // l ptr is +1 b/c we already put the lowest in there, ignore it for now
+ // r ptr is -2 b/c we already put the biggest and the median there
+ C *l = left + 1, *r = right-2;
+
+ // move l and r until they have something to do
+ while (lt(median, *(r-1))) {
--- End diff --
Note the original code doesn't check the bounds because we know the `lt` check will stop before `l < r` in any case (since !(median < median).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] trafficserver pull request: TS 3867 - Improved qsort
Posted by AZNova <gi...@git.apache.org>.
Github user AZNova commented on the pull request:
https://github.com/apache/trafficserver/pull/286#issuecomment-137756663
Updated the commit. Moved the swap() above its initial usage. Clarified comments. Included amc's updated test_vec.cc which calls the new qsort as part of regression testing.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] trafficserver pull request: TS 3867 - Improved qsort
Posted by SolidWallOfCode <gi...@git.apache.org>.
Github user SolidWallOfCode commented on a diff in the pull request:
https://github.com/apache/trafficserver/pull/286#discussion_r38668014
--- Diff: lib/ts/Vec.h ---
@@ -964,41 +965,71 @@ qsort_Vec(C *left, C *right, bool (*lt)(C, C))
}
}
} else {
- C *i = left + 1, *j = right - 1;
- C x = *left;
- for (;;) {
- while (lt(x, *j))
- j--;
- while (i < j && lt(*i, x))
- i++;
- if (i >= j)
- break;
- C t = *i;
- *i = *j;
- *j = t;
- i++;
- j--;
+ C *center = left + ((right - left) / 2);
+ C median;
+
+ // find the median
+ if (lt(*center, *left)){ // order left and center
+ swap(center, left);
+ }
+ if (lt(*(right-1), *left)){ // order left and right
+ swap(right-1, left);
+ }
+ if (lt(*(right-1), *center)){ // order right and center
+ swap((right-1), center);
+ }
+ swap(center, right-2); // stash the median one from the right for now
+ median = *(right-2); // and that's the median of the 3
+
+ // now partition, pivoting on the median value
+ // l ptr is +1 b/c we already put the lowest in there, ignore it for now
--- End diff --
Not quite right - l (left) is not necessarily the lowest value in the span, but we do know !(median < left) which makes it valid for being in its position relative to the pivot (median). Same for right-1, !(right < median) so it's correctly grouped already. (This is about the comment, the code is correct)
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] trafficserver pull request: TS 3867 - Improved qsort
Posted by AZNova <gi...@git.apache.org>.
Github user AZNova commented on the pull request:
https://github.com/apache/trafficserver/pull/286#issuecomment-137493566
I have updated this pull request with a new commit. I ran all of the regression tests using 'make check', and all passed. I have tested this with approx 10k certs and it worked fine. I have also deployed this to one of our servers in our production environment with no issues.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---