4
\$\begingroup\$

I recently decided to make my own implementation of the Introsort sorting algorithm for educational purposes. Here's what I ended up with (apologies for the lack of comments):

#include <cmath>
#include <functional>

namespace __Introsort
{
template <typename T> using Compare = std::function<bool(T const &, T const &)>;

template <typename Container, typename T = typename Container::value_type>
void insertionSort(Container &arr, Compare<T> comp, size_t start, size_t end)
{
    for (size_t i = start + 1; i <= end; i++)
    {
        T temp = arr[i];
        size_t j = i;

        if (comp(arr[i], arr[start]))
        {
            // arr[i] will land at the start. Don't bother to compare values.
            // Just shift everything to the right.
            for (; j > start; j--)
            {
                arr[j] = arr[j - 1];
            }

            arr[j] = temp;
        }
        else
        {
            // arr[start] serves as a natural sentinel. Don't bother to test indices.
            for (; !comp(arr[j - 1], temp); j--)
            {
                arr[j] = arr[j - 1];
            }

            arr[j] = temp;
        }
    }
}

inline size_t heapNodeParent(size_t offset, size_t node)
{
    // Simplification of (node - offset - 1) / 2 + offset
    return (node + offset - 1) / 2;
}

inline size_t heapNodeLeftChild(size_t offset, size_t node)
{
    // Simplification of 2 * (node - offset) + offset + 1
    return 2 * node - offset + 1;
}

template <typename Container, typename T = typename Container::value_type>
void siftDown(Container &arr, Compare<T> comp, size_t offset, size_t start, size_t end)
{
    size_t node = start;

    while (heapNodeLeftChild(offset, node) <= end)
    {
        size_t swap = node;
        size_t leftChild = heapNodeLeftChild(offset, node);

        if (comp(arr[swap], arr[leftChild]))
        {
            swap = leftChild;
        }
        if (leftChild + 1 <= end && comp(arr[swap], arr[leftChild + 1]))
        {
            swap = leftChild + 1;
        }
        if (swap == node)
        {
            return;
        }

        std::swap(arr[swap], arr[node]);
        node = swap;
    }
}

template <typename Container, typename T = typename Container::value_type>
void heapify(Container &arr, Compare<T> comp, size_t start, size_t end)
{
    size_t node = heapNodeParent(start, end);

    while (node > start)
    {
        siftDown(arr, comp, start, node, end);
        node = node - 1;
    }

    siftDown(arr, comp, start, node, end);
}

template <typename Container, typename T = typename Container::value_type>
void heapSort(Container &arr, Compare<T> comp, size_t start, size_t end)
{
    heapify(arr, comp, start, end);

    while (end > start)
    {
        std::swap(arr[end], arr[start]);
        end = end - 1;
        siftDown(arr, comp, start, start, end);
    }
}

// Uses Hoare's partitioning scheme for quick sort
template <typename Container, typename T = typename Container::value_type>
size_t partition(Container &arr, Compare<T> comp, size_t start, size_t end)
{
    // Pivot value
    T pivot = arr[(start + end) / 2];

    size_t i = start - 1;
    size_t j = end + 1;

    while (true)
    {
        do
        {
            i++;
        } while (comp(arr[i], pivot));
        do
        {
            j--;
        } while (comp(pivot, arr[j]));

        if (i >= j)
        {
            return j;
        }

        std::swap(arr[i], arr[j]);
    }
}

template <typename Container, typename T = typename Container::value_type>
void introSortHelper(Container &arr, Compare<T> comp, size_t start, size_t end, size_t maxdepth)
{
    if (end - start + 1 < 16)
    {
        insertionSort(arr, comp, start, end);
    }
    else if (maxdepth == 0)
    {
        heapSort(arr, comp, start, end);
    }
    else
    {
        size_t p = partition(arr, comp, start, end);
        introSortHelper(arr, comp, start, p, maxdepth - 1);
        introSortHelper(arr, comp, p + 1, end, maxdepth - 1);
    }
}

template <typename Container, typename T = typename Container::value_type>
void introSort(Container &arr, Compare<T> comp = std::less<T>())
{
    introSortHelper(arr, comp, 0, arr.size() - 1, 2 * static_cast<size_t>(std::log2(arr.size())));
}
} // namespace __Introsort

using __Introsort::introSort;

When I tried to benchmark it against std::sort (GNU libstdc++ implementation), I found out that it's on average 4.2 times slower than std::sort. I believe that std::sort generally uses Introsort as well, so I'm not quite sure what's causing this massive slowdown. A minor slowdown like 1.5x is expected, but this is far too big of a slowdown for the same algorithm. It would be nice if someone could help me understand why there's such a big slowdown here.

As an extra note: Earlier this Introsort algorithm used Shellsort instead of Insertion sort when array size was lower than 16, and that turned out to be slower than using Insertion sort, much to my surprise.

For anyone wondering, here's the code I used to benchmark this:

#include "introsort.h"
#include <chrono>
#include <functional>
#include <iostream>
#include <vector>

template <typename T> bool vecEqual(std::vector<T> const &vec1, std::vector<T> const &vec2)
{
    if (vec1.size() != vec2.size())
    {
        return false;
    }

    for (size_t i = 0; i < vec1.size(); i++)
    {
        if (vec1[i] != vec2[i])
        {
            return false;
        }
    }

    return true;
}

int main()
{
    std::vector<int> vec = {
        541, 512, 875, 506, 77,  119, 755, 49,  146, 268, 179, 681, 542, 458, 396, 113, 898, 810,
        586, 830, 611, 117, 930, 824, 681, 792, 249, 592, 323, 718, 316, 116, 842, 791, 327, 567,
        583, 707, 342, 40,  198, 370, 879, 61,  252, 447, 665, 976, 7,   115, 820, 334, 562, 486,
        229, 184, 965, 723, 886, 121, 791, 603, 617, 569, 187, 321, 826, 119, 714, 930, 786, 1,
        692, 217, 762, 985, 820, 23,  656, 697, 701, 992, 953, 592, 829, 988, 689, 399, 566, 511,
        677, 422, 625, 275, 158, 849, 271, 676, 775, 439, 696, 86,  853, 546, 424, 615, 96,  288,
        804, 906, 563, 423, 971, 460, 45,  696, 423, 752, 745, 705, 403, 869, 138, 27,  107, 174,
        352, 985, 947, 149, 845, 286, 826, 130, 941, 604, 8,   209, 635, 15,  297, 262, 688, 164,
        356, 933, 708, 473, 669, 123, 235, 336, 302, 334, 498, 766, 885, 887, 250, 621, 699, 178,
        352, 581, 416, 458, 978, 853, 645, 245, 579, 57,  647, 604, 216, 888, 290, 952, 913, 152,
        288, 523, 280, 2,   354, 546, 239, 367, 40,  917, 985, 197, 770, 101, 266, 532, 230, 101,
        964, 801, 637, 102, 651, 763, 976, 142, 750, 9,   486, 53,  28,  908, 561, 850, 364, 864,
        687, 922, 229, 460, 396, 818, 672, 211, 620, 695, 332, 657, 910, 71,  854, 104, 615, 197,
        475, 500, 673, 281, 463, 840, 269, 531, 242, 512, 785, 681, 592, 875, 362, 750, 168, 23,
        82,  963, 883, 8,   480, 709, 117, 744, 974, 388, 191, 486, 480, 684, 29,  959, 706, 64,
        636, 390, 635, 348, 692, 815, 700, 514, 824, 816, 329, 388, 322, 796, 244, 790, 222, 395,
        359, 289, 956, 928, 736, 487, 913, 817, 343, 552, 236, 30,  34,  131, 417, 323, 38,  80,
        802, 866, 575, 670, 555, 990, 122, 341, 882, 164, 790, 152, 81,  817, 423, 281, 961, 185,
        123, 349, 254, 696, 666, 237, 3,   693, 563, 643, 70,  898, 294, 739, 99,  823, 416, 10,
        764, 955, 794, 526, 239, 659, 588, 901, 616, 34,  345, 108, 966, 351, 428, 490, 820, 752,
        567, 949, 109, 758, 215, 219, 56,  237, 500, 678, 887, 515, 24,  961, 42,  220, 314, 226,
        293, 499, 943, 392, 192, 271, 98,  164, 169, 3,   196, 721, 71,  617, 311, 5,   219, 292,
        863, 970, 341, 567, 956, 940, 81,  525, 28,  646, 908, 489, 448, 27,  857, 221, 580, 132,
        586, 613, 287, 127, 823, 618, 271, 16,  335, 72,  501, 808, 435, 293, 268, 755, 244, 722,
        205, 192, 419, 424, 244, 70,  633, 593, 601, 111, 916, 738, 503, 729, 439, 77,  981, 563,
        281, 370, 972, 701, 914, 167, 305, 27,  192, 298, 603, 744, 701, 323, 519, 438, 712, 587,
        253, 485, 455, 379, 499, 852, 21,  336, 939, 502, 70,  539, 291, 56,  705, 357, 289, 655,
        573, 887, 771, 1,   981, 70,  57,  580, 526, 557, 397, 324, 14,  372, 378, 439, 488, 663,
        515, 951, 586, 927, 876, 956, 115, 620, 663, 480, 768, 793, 949, 797, 244, 585, 901, 949,
        51,  614, 456, 89,  742, 883, 970, 462, 630, 553, 948, 205, 290, 969, 442, 705, 970, 537,
        498, 625, 524, 152, 681, 833, 114, 388, 427, 548, 409, 641, 463, 614, 208, 741, 458, 548,
        319, 971, 547, 240, 552, 489, 917, 527, 776, 114, 47,  58,  836, 551, 197, 69,  315, 450,
        616, 408, 318, 146, 55,  969, 757, 654, 162, 82,  369, 636, 766, 267, 191, 324, 946, 779,
        652, 463, 879, 623, 575, 370, 678, 983, 567, 256, 258, 619, 115, 745, 214, 268, 468, 372,
        399, 691, 164, 282, 398, 627, 328, 465, 263, 407, 252, 546, 399, 608, 285, 572, 485, 665,
        176, 401, 767, 658, 121, 906, 87,  713, 556, 698, 295, 245, 144, 882, 938, 514, 431, 190,
        614, 559, 842, 273, 476, 90,  700, 92,  682, 46,  33,  445, 9,   482, 369, 909, 180, 985,
        346, 985, 899, 213, 831, 48,  327, 507, 724, 509, 990, 335, 198, 643, 54,  82,  164, 811,
        71,  362, 416, 738, 715, 32,  53,  621, 79,  664, 988, 998, 185, 985, 210, 109, 214, 487,
        681, 53,  973, 501, 911, 867, 887, 4,   644, 267, 427, 121, 685, 661, 155, 957, 274, 307,
        790, 308, 968, 360, 179, 157, 875, 678, 350, 506, 746, 156, 176, 195, 834, 704, 693, 539,
        205, 322, 580, 668, 532, 105, 895, 425, 876, 648, 192, 508, 366, 469, 147, 151, 695, 644,
        276, 780, 820, 693, 573, 631, 934, 885, 164, 948, 592, 775, 949, 818, 176, 228, 914, 336,
        553, 74,  801, 635, 269, 404, 818, 111, 809, 948, 454, 780, 818, 692, 961, 88,  946, 997,
        804, 993, 846, 390, 386, 129, 358, 757, 307, 947, 657, 506, 79,  520, 999, 933, 147, 607,
        122, 296, 165, 360, 583, 299, 273, 838, 619, 875, 576, 962, 177, 406, 195, 315, 737, 991,
        140, 587, 466, 780, 619, 104, 426, 825, 842, 136, 747, 542, 208, 605, 95,  808, 978, 748,
        36,  231, 64,  104, 588, 700, 552, 183, 224, 741, 614, 484, 149, 175, 966, 654, 538, 381,
        139, 677, 262, 638, 781, 980, 87,  590, 808, 615, 601, 46,  349, 221, 34,  125, 269, 524,
        7,   898, 903, 391, 810, 550, 201, 956, 606, 457, 886, 149, 705, 529, 399, 428, 731, 180,
        864, 251, 326, 281, 261, 282, 386, 837, 681, 996, 749, 968, 74,  578, 928, 796, 158, 136,
        733, 779, 748, 583, 855, 535, 491, 655, 796, 742, 461, 165, 380, 76,  496, 694, 606, 329,
        643, 41,  649, 37,  66,  211, 615, 16,  483, 90,  855, 954, 885, 442, 245, 413, 753, 88,
        130, 522, 149, 302, 133, 542, 685, 508, 424, 547, 686, 206, 517, 179, 749, 120, 950, 834,
        830, 112, 582, 707, 481, 124, 844, 849, 14,  704, 127, 611, 378, 850, 911, 904, 564, 424,
        185, 752, 82,  69,  205, 39,  322, 472, 323, 339
    };

    std::vector<int> vecTemp;

    int runs = 100;
    long total = 0;
    long avg1;
    long avg2;

    for (int i = 0; i < runs; i++)
    {
        vecTemp = vec;
        auto start = std::chrono::high_resolution_clock::now();
        introSort(vecTemp);
        auto end = std::chrono::high_resolution_clock::now();
        total += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
    }

    avg1 = total / runs;
    total = 0;

    for (int i = 0; i < runs; i++)
    {
        vecTemp = vec;
        auto start = std::chrono::high_resolution_clock::now();
        std::sort(vecTemp.begin(), vecTemp.end());
        auto end = std::chrono::high_resolution_clock::now();
        total += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
    }
    
    avg2 = total / runs;

    std::cout << "Custom Introsort: " << avg1 << "\nC++ Standard Library Sort: " << avg2 << "\n";
}
```
Improve this question
\$\endgroup\$
2
  • \$\begingroup\$ Please do not edit the question, especially the code, after an answer has been posted. Changing the question may cause answer invalidation. Everyone needs to be able to see what the reviewer was referring to. What to do after the question has been answered. \$\endgroup\$
    – pacmaninbw
    Jun 5, 2022 at 17:58
  • \$\begingroup\$ Ah, sorry about that. Will keep it in mind. \$\endgroup\$
    – Famiu
    Jun 5, 2022 at 19:19

3 Answers 3

Reset to default
2
\$\begingroup\$

One of the major reasons the native C++ std::sort() is faster than qsort() inherited from C is that the latter calls the comparator using a pointer.

While that is excellent for reducing binary footprint, it costs a lot, not really due to the indirect call itself, but due to all the optimization opportunities lost because it is not inlined and available for optimization.

While you don't use any raw function-pointers, you use std::function in your interface, which has the same performance implications. Actually, it is a bit more versatile, and thus costs slightly more.

Template your code to accept any callable and use it directly, and performance should improve significantly.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ That shouldn't cause a slowdown compared to the default std::sort() since both my implementation and std::sort use the std::less comparison function by default. right? \$\endgroup\$
    – Famiu
    Jun 5, 2022 at 17:12
  • \$\begingroup\$ @Famiu Both use the std::less function-object by default, but yours hides it in a std::function, and you pay the penalty of dynamic dispatch instead of static dispatch, the latter additionally being trivially inlined. \$\endgroup\$
    – Deduplicator
    Jun 5, 2022 at 18:55
  • \$\begingroup\$ Changing it to accept any callable does in fact make the performance basically equal. Thank you so much! \$\endgroup\$
    – Famiu
    Jun 5, 2022 at 19:25
4
\$\begingroup\$

  • I strongly recommend to try std::partition and std::make_heap/std::sort_heap to see what is suboptimal in your implementation.

  • An implementation of insertion_sort is suboptimal. Every iteration of an inner loop does two tests - one for index, and another for values. It is possible to get away with only one:

      if (comp(arr[i], arr[start])) {
      // arr[i] shall land at start. Don't bother to compare values.
      // Just shift everything to the right.
  } else {
      // arr[start] serves as a natural sentinel. Don't bother to
      // test indices.
  }

  • An implementation of heap related functions is definitely wrong. They only work if start is 0. When computing the children you must offset node by start.

    This is masked by the curious fact: with your test array heapSort is never called. Why does it happen, I have no idea, but it rings an unpleasant bell.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Using std::partition doesn't make a difference. heapSort is never called so I doubt using std::make_heap / std::sort_heap would make a difference either. Thanks for pointing out the bugs in my heapSort and insertionSort implementation. I changed them and the performance improved by quite a bit, still much slower than std::sort though. \$\endgroup\$
    – Famiu
    Jun 4, 2022 at 5:54
-1
\$\begingroup\$

I think insertion sort is the bottleneck. I think your implementation makes assignments and comparisons too much.

This is my (simplified) implementation

void insertion_sort(std::vector<int>& v) {
    if (v.empty()) return;
    for (size_t i = 1; i < v.size(); ++i) {
        int key = v[i];
        auto j = i;
        while (j != 0 && v[j - 1] >= key) {
            std::swap(v[j - 1], v[j]);
            --j;
        }
        v[j] = key;
    }
}

I benchmarked my implementation (link) combined with merge sort(link), I saw the same level of performance with std::sort

And since your heapSort is not called, it means that your time complexity is O(n^2), so it should be slower

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Not only is your algorithm not applicable in my case since it sorts the full vector instead of part of it, when I adapt it for introsort, it ends up to be 2-3x slower than my implementation. It also does much more swaps since using multiple std::swaps is much slower than just shifting all values by 1. \$\endgroup\$
    – Famiu
    Jun 5, 2022 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.