HPX set_difference, set_intersection failure cases

[hkaiser]

Hello,

I am an intern on the Visual C++ Libraries Team this summer and have been working on implementing some of their parallel algorithms. While working on implementing the set operations in parallel, I was comparing the performance of my implementation to hpx’s. In doing so, I found some cases in which I got an “Access violation writing location” or “RangeChecks implementation code detected an out of range array access” exception (attempting to run the same executable multiple times resulted in almost always throwing this exception). I don’t believe this is expected behavior, so Billy O’Neal suggested I email you my findings.

The benchmarking program I was using can be found attached. I would comment out one of the algorithms’ calls to test the performance of the other. The specific cases in which I fairly consistently got an exception (in 5-6 tries running the executable, I got the exception every time) were:
set_difference
n=5: all cases
n=50: Cases 1-6, 9
set_intersection:
n=50: Case 9
n=500000: Case 9
n=5000000: Case 9
n=50000000: Case 9

There were some cases where running the executable 5-6 times would finish and allow me to collect data for that case, but I’m afraid I didn’t record those (I was initially just interested in gathering benchmarking results, and it was later suggested that I should notify you of these issues).

Please let me know if you need more information.

Best,

Miya Natsuhara
mailto:t-minat@microsoft.com

[hkaiser]

Here is the code that was attached to the original email:

#include <stdlib.h>
#include <hpx/hpx.hpp>
#include <hpx/include/parallel_set_operations.hpp>
#include <hpx/hpx_init.hpp>
#include <algorithm>
#include <execution>
#include <iterator>
#include <numeric>
#include <vector>
#include <iostream>

using namespace std;

#pragma once

#include <stdio.h>
#include <chrono>

const auto read_char_as_bool = [](char c) { return c != 0; };

class stopwatch {
	std::chrono::high_resolution_clock::time_point startTime;
	std::chrono::high_resolution_clock::time_point stopTime;

public:
	stopwatch()
		: startTime()
		, stopTime()
	{ }

	stopwatch(const stopwatch&) = delete;
	stopwatch& operator=(const stopwatch&) = delete;

	void start() {
		startTime = std::chrono::high_resolution_clock::now();
	}

	void stop() {
		stopTime = std::chrono::high_resolution_clock::now();
	}

	std::chrono::duration<double> time_taken() const {
		return stopTime - startTime;
	}

	double compare(const stopwatch& s) {
		return static_cast<double>(s.time_taken().count()) / time_taken().count();
	}

	void print(const char * const action) const {
		printf("%fs taken by %s\n", time_taken().count(), action);
	}
};

int main(int argc, char* argv[])
{
	// Configure application-specific options
	boost::program_options::options_description
		desc_commandline("Usage: " HPX_APPLICATION_STRING " [options]");

	desc_commandline.add_options()
		("n-value",
			boost::program_options::value<std::uint64_t>()->default_value(10),
			"n value for the Fibonacci function")
		;

	// Initialize and run HPX
	return hpx::init(desc_commandline, argc, argv);
}

void time_results(size_t testSize) {
	cout << "_____n = " << testSize << "_____\n";
	int numRuns = 50;
	vector<__int32> longList(testSize);
	vector<__int32> shortList(testSize / 2);
	vector<__int32> result(testSize);
	stopwatch watch;
	iota(longList.begin(), longList.end(), 1);
	iota(shortList.begin(), shortList.end(), static_cast<int>(testSize / 2));
	double seqAvgTimePass = 0;
	double parAvgTimePass = 0;

	// Case 1:
	// Range 1: [1, 2, ..., testSize]
	// Range 2: [testSize / 2, (testSize / 2) + 1, ..., testSize (or testSize - )]
	watch.start();
	for (int i = 0; i < numRuns; ++i) {
		auto res = hpx::parallel::set_difference(hpx::parallel::execution::par, longList.begin(), longList.end(), shortList.begin(), shortList.end(), result.begin());
		//auto res = hpx::parallel::set_intersection(hpx::parallel::execution::par, longList.begin(), longList.end(), shortList.begin(), shortList.end(), result.begin());
	}
	watch.stop();
	parAvgTimePass = watch.time_taken().count();

	parAvgTimePass /= numRuns;

	cout << "For Range 1 superset of Range 2 (overlapping portion at end), averaged across " << numRuns << " runs:\n";
	cout << "Parallel: " << parAvgTimePass << "\n\n";

	// Case 2:
	// Range 1: [testSize / 2, (testSize / 2) + 1, ..., testSize - 1 (or testSize - 2)]
	// Range 2: [1, 2, ..., testSize]
	watch.start();
	for (int i = 0; i < numRuns; ++i) {
		auto res = hpx::parallel::set_difference(hpx::parallel::execution::par, shortList.begin(), shortList.end(), longList.begin(), longList.end(), result.begin());
		//auto res = hpx::parallel::set_intersection(hpx::parallel::execution::par, shortList.begin(), shortList.end(), longList.begin(), longList.end(), result.begin());
	}
	watch.stop();
	parAvgTimePass = watch.time_taken().count();

	parAvgTimePass /= numRuns;

	cout << "For Range 1 subset of Range 2 (overlapping portion at end), averaged across " << numRuns << " runs:\n";
	cout << "Parallel: " << parAvgTimePass << "\n\n";

	__int32 temp = 2;
	for (auto& elem : shortList) {
		elem = temp;
		temp += 2;
	}

	// Case 3: 
	// Range 1: [1, 2, ..., testSize]
	// Range 2: [2, 4, ..., testSize (or testSize - 1)]
	watch.start();
	for (int i = 0; i < numRuns; ++i) {
		auto res = hpx::parallel::set_difference(hpx::parallel::execution::par, longList.begin(), longList.end(), shortList.begin(), shortList.end(), result.begin());
		//auto res = hpx::parallel::set_intersection(hpx::parallel::execution::par, longList.begin(), longList.end(), shortList.begin(), shortList.end(), result.begin());
	}
	watch.stop();
	parAvgTimePass = watch.time_taken().count();

	parAvgTimePass /= numRuns;

	cout << "For Range 1 superset of Range 2 (overlapping portions spread throughout), averaged across " << numRuns << " runs:\n";
	cout << "Parallel: " << parAvgTimePass << "\n\n";

	// Case 4:
	// Range 1: [2, 4, ..., testSize (or testSize - 1]
	// Range 2: [1, 2, ..., testSize]
	watch.start();
	for (int i = 0; i < numRuns; ++i) {
		auto res = hpx::parallel::set_difference(hpx::parallel::execution::par, shortList.begin(), shortList.end(), longList.begin(), longList.end(), result.begin());
		//auto res = hpx::parallel::set_intersection(hpx::parallel::execution::par, shortList.begin(), shortList.end(), longList.begin(), longList.end(), result.begin());
	}
	watch.stop();
	parAvgTimePass = watch.time_taken().count();

	parAvgTimePass /= numRuns;

	cout << "For Range 1 subset of Range 2 (overlapping portions spread throughout), averaged across " << numRuns << " runs:\n";
	cout << "Parallel: " << parAvgTimePass << "\n\n";

	iota(shortList.begin(), shortList.end(), 1);

	// Case 5: 
	// Range 1: [1, 2, ..., testSize]
	// Range 2: [1, 2, ..., testSize / 2]
	watch.start();
	for (int i = 0; i < numRuns; ++i) {
		auto res = hpx::parallel::set_difference(hpx::parallel::execution::par, longList.begin(), longList.end(), shortList.begin(), shortList.end(), result.begin());
		//auto res = hpx::parallel::set_intersection(hpx::parallel::execution::par, longList.begin(), longList.end(), shortList.begin(), shortList.end(), result.begin());
	}
	watch.stop();
	parAvgTimePass = watch.time_taken().count();

	parAvgTimePass /= numRuns;

	cout << "For Range 1 superset of Range 2 (overlapping portion at beginning), averaged across " << numRuns << " runs:\n";
	cout << "Parallel: " << parAvgTimePass << "\n\n";

	// Case 6:
	// Range 1: [1, 2, ..., testSize / 2]
	// Range 2: [1, 2, ..., testSize]
	watch.start();
	for (int i = 0; i < numRuns; ++i) {
		auto res = hpx::parallel::set_difference(hpx::parallel::execution::par, shortList.begin(), shortList.end(), longList.begin(), longList.end(), result.begin());
		//auto res = hpx::parallel::set_intersection(hpx::parallel::execution::par, shortList.begin(), shortList.end(), longList.begin(), longList.end(), result.begin());
	}
	watch.stop();
	parAvgTimePass = watch.time_taken().count();

	parAvgTimePass /= numRuns;

	cout << "For Range 1 subset of Range 2 (overlapping portion at beginning), averaged across " << numRuns << " runs:\n";
	cout << "Parallel: " << parAvgTimePass << "\n\n";

	vector<size_t> falseList(testSize, 0U);

	// Case 7:
	// Range 1: [1, 2, ..., testSize]
	// Range 2: [0, 0, ..., 0]
	watch.start();
	for (int i = 0; i < numRuns; ++i) {
		auto res = hpx::parallel::set_difference(hpx::parallel::execution::par, longList.begin(), longList.end(), falseList.begin(), falseList.end(), result.begin());
		//auto res = hpx::parallel::set_intersection(hpx::parallel::execution::par, longList.begin(), longList.end(), falseList.begin(), falseList.end(), result.begin());
	}
	watch.stop();
	parAvgTimePass = watch.time_taken().count();

	parAvgTimePass /= numRuns;

	cout << "For Range 1 and Range 2 same size, but disjoint, averaged across " << numRuns << " runs:\n";
	cout << "hpx Parallel: " << parAvgTimePass << "\n\n";

	// Case 8: 
	// Range 1: [1, 2, ..., testSize]
	// Range 2: [1, 2, ..., testSize]
	watch.start();
	for (int i = 0; i < numRuns; ++i) {
		auto res = hpx::parallel::set_difference(hpx::parallel::execution::par, longList.begin(), longList.end(), longList.begin(), longList.end(), result.begin());
		//auto res = hpx::parallel::set_intersection(hpx::parallel::execution::par, longList.begin(), longList.end(), longList.begin(), longList.end(), result.begin());
	}
	watch.stop();
	parAvgTimePass = watch.time_taken().count();

	parAvgTimePass /= numRuns;

	cout << "For Range 1 and Range 2 equal, averaged across " << numRuns << " runs:\n";
	cout << "hpx Parallel: " << parAvgTimePass << "\n\n";
	
	int testSizeInt = static_cast<int>(testSize);
	fill(longList.begin(), longList.begin() + testSizeInt / 4, 0);
	fill(longList.begin() + testSizeInt / 4, longList.begin() + testSizeInt / 2, 1);
	fill(longList.begin() + testSizeInt / 2, longList.begin() + 3 * testSizeInt / 4, 2);
	fill(longList.begin() + 3 * testSizeInt / 4, longList.end(), 3);

	// Case 9:
	// Range 1: [1, 2, ..., testSize]
	// Range 2: [0, 0, ..., 0, 1, 1, ..., 1, 2, 2, ..., 2, 3, 3, ..., 3]
	watch.start();
	for (int i = 0; i < numRuns; ++i) {
		auto res = hpx::parallel::set_difference(hpx::parallel::execution::par, longList.begin(), longList.end(), shortList.begin(), shortList.end(), result.begin());
		//auto res = hpx::parallel::set_intersection(hpx::parallel::execution::par, longList.begin(), longList.end(), shortList.begin(), shortList.end(), result.begin());

	}
	watch.stop();
	parAvgTimePass = watch.time_taken().count();

	parAvgTimePass /= numRuns;

	cout << "For Range 1 with duplicates of elements in Range 2, Range 2 smaller size, averaged across " << numRuns << " runs:\n";
	cout << "hpx Parallel: " << parAvgTimePass << "\n\n";
	
}

int hpx_main(boost::program_options::variables_map& vm)
{
	cout << "Made it here\n";
	for (size_t n = 10; n <= 100'000'000; n *= 10) {
		time_results(n / 2);
	}
	cout << "stop here\n";

	string s;
	cin >> s;

	return hpx::finalize(); // Handles HPX shutdown
}