InitHEADmain

5 files changed, 443 insertions, 0 deletions

diff --git a/Homework/cs3460/array_perf/CMakeLists.txt b/Homework/cs3460/array_perf/CMakeLists.txt
new file mode 100644
index 0000000..4f85c75
--- /dev/null
+++ b/Homework/cs3460/array_perf/CMakeLists.txt
@@ -0,0 +1,71 @@
+cmake_minimum_required(VERSION 3.12)
+
+set(PROJECT_NAME ArrayPerformance)
+set(UNIT_TEST_RUNNER UnitTestRunner)
+
+project(${PROJECT_NAME})
+
+set(HEADER_FILES sortutils.hpp)
+set(SOURCE_FILES sortutils.cpp)
+set(UNIT_TEST_FILES TestPerformance.cpp)
+
+add_executable(${PROJECT_NAME} ${SOURCE_FILES} ${HEADER_FILES} main.cpp)
+add_executable(${UNIT_TEST_RUNNER} ${SOURCE_FILES} ${HEADER_FILES} ${UNIT_TEST_FILES})
+
+set_property(TARGET ${PROJECT_NAME} PROPERTY CXX_STANDARD 20)
+set_property(TARGET ${UNIT_TEST_RUNNER} PROPERTY CXX_STANDARD 20)
+
+if (CMAKE_CXX_COMPILER_ID MATCHES "MSVC")
+    set_target_properties(${PROJECT_NAME} PROPERTIES LINK_FLAGS "/STACK:10000000")
+    target_compile_options(${PROJECT_NAME} PRIVATE /W4 /permissive-)
+    set_target_properties(${UNIT_TEST_RUNNER} PROPERTIES LINK_FLAGS "/STACK:10000000")
+    target_compile_options(${UNIT_TEST_RUNNER} PRIVATE /W4 /permissive-)
+elseif (CMAKE_CXX_COMPILER_ID MATCHES "GNU")
+    target_compile_options(${PROJECT_NAME} PRIVATE -Wall -Wextra -pedantic -Wl,--stack,10000000 -O1 -g)
+    target_compile_options(${UNIT_TEST_RUNNER} PRIVATE -Wall -Wextra -pedantic -Wl,--stack,10000000 -O1)
+elseif (CMAKE_CXX_COMPILER_ID MATCHES "Clang")
+    target_compile_options(${PROJECT_NAME} PRIVATE -Wall -Wextra -pedantic -Wl,--stack,10000000 -O3)
+    target_compile_options(${UNIT_TEST_RUNNER} PRIVATE -Wall -Wextra -pedantic -Wl,--stack,10000000 -O3)
+endif()
+
+find_program(CLANG_FORMAT "clang-format")
+if (CLANG_FORMAT)
+	message("CLANG-FORMAT found at: " ${CLANG_FORMAT})
+	unset(SOURCE_FILES_PATHS)
+	foreach(SOURCE_FILE ${SOURCE_FILES} ${HEADER_FILES} ${UNIT_TEST_FILES} main.cpp)
+		get_source_file_property(WHERE ${SOURCE_FILE} LOCATION)
+		set(SOURCE_FILES_PATHS ${SOURCE_FILES_PATHS} ${WHERE})
+	endforeach()
+
+	add_custom_target(
+		ClangFormat
+		COMMAND ${CLANG_FORMAT}
+		-i
+		-style=file
+		${SOURCE_FILES_PATHS})
+
+	add_dependencies(${PROJECT_NAME} ClangFormat)
+else()
+	message("Unable to find Clang-Format")
+endif()
+
+include(FetchContent)
+FetchContent_Declare(
+  googletest
+  GIT_REPOSITORY 	https://github.com/google/googletest.git
+  GIT_TAG			release-1.11.0
+)
+
+FetchContent_Declare(
+  fmt
+  GIT_REPOSITORY    https://github.com/fmtlib/fmt.git
+  GIT_TAG           9.1.0
+)
+
+FetchContent_MakeAvailable(fmt)
+target_link_libraries(${PROJECT_NAME} PRIVATE fmt::fmt)
+
+set(gtest_force_shared_crt ON CACHE BOOL "" FORCE)
+FetchContent_MakeAvailable(googletest)
+
+target_link_libraries(${UNIT_TEST_RUNNER} PRIVATE fmt::fmt gtest_main)
diff --git a/Homework/cs3460/array_perf/TestPerformance.cpp b/Homework/cs3460/array_perf/TestPerformance.cpp
new file mode 100644
index 0000000..302ab64
--- /dev/null
+++ b/Homework/cs3460/array_perf/TestPerformance.cpp
@@ -0,0 +1,54 @@
+#include "sortutils.hpp"

+

+#include "gtest/gtest.h"

+#include <algorithm>

+#include <random>

+

+constexpr auto MIN_VALUE = -10'000'000;

+constexpr auto MAX_VALUE = 10'000'000;

+

+int main(int argc, char* argv[])

+{

+    testing::InitGoogleTest(&argc, argv);

+    return RUN_ALL_TESTS();

+}

+

+SourceArray generateRandomArray()

+{

+    std::default_random_engine engine{ 0u };

+    std::uniform_int_distribution<> dist{ MIN_VALUE, MAX_VALUE };

+

+    SourceArray array;

+    std::generate(array.begin(), array.end(), [&] { return dist(engine); });

+    return array;

+}

+

+TEST(OrganPipeArray, DoesGenerateCorrectly)

+{

+    auto sourceArray = generateRandomArray();

+    std::sort(sourceArray.begin(), sourceArray.end());

+    auto array = sourceArray;

+    organPipeStdArray(array);

+

+    for (auto i = 0ul; i < sourceArray.size() / 2; i++)

+    {

+        ASSERT_EQ(sourceArray[i], array[i]) << "Organ pipe changed first half of array at position " << i;

+    }

+

+    for (std::size_t first = 0ul, second = array.size() - 1; first < second; first++, second--)

+    {

+        ASSERT_EQ(array[first], array[second]) << "Organ pipe not symmetric at positions " << first << " and " << second;

+    }

+}

+

+TEST(RawArray, DoesInitializeFromStdArrayCorrectly)

+{

+    const auto sourceArray = generateRandomArray();

+    int dest[HOW_MANY_ELEMENTS];

+    initializeRawArrayFromStdArray(sourceArray, dest);

+

+    for (auto i = 0ul; i < sourceArray.size(); i++)

+    {

+        ASSERT_EQ(sourceArray[i], dest[i]) << "Raw array differs from source array at position " << i;

+    }

+}

diff --git a/Homework/cs3460/array_perf/main.cpp b/Homework/cs3460/array_perf/main.cpp
new file mode 100644
index 0000000..1441751
--- /dev/null
+++ b/Homework/cs3460/array_perf/main.cpp
@@ -0,0 +1,44 @@
+#include "sortutils.hpp"
+
+#include <algorithm>
+#include <cmath>
+#include <iostream>
+
+const int MIN_DIST = static_cast<int>(-1e+7);
+const int MAX_DIST = static_cast<int>(1e+7);
+
+/**
+ * @param SourceArray source: the data to initialize with random elements
+ * @return void: set source's elements between MIN_DIST, MAX_DIST
+ */
+void randomizeArray(SourceArray& source)
+{
+    std::uniform_int_distribution<int> distribution(MIN_DIST, MAX_DIST);
+    std::default_random_engine generator;
+    std::generate(std::execution::par, source.begin(), source.end(), [&distribution, &generator]() { return distribution(generator); });
+}
+
+int main()
+{
+    SourceArray randomizedArray, sorted, reversed, organPipe, rotated;
+
+    randomizeArray(randomizedArray);
+
+    std::copy(randomizedArray.begin(), randomizedArray.end(), sorted.begin());
+    std::sort(sorted.begin(), sorted.end());
+
+    std::copy(sorted.begin(), sorted.end(), reversed.begin());
+    std::reverse(reversed.begin(), reversed.end());
+
+    std::copy(sorted.begin(), sorted.end(), organPipe.begin());
+    organPipeStdArray(organPipe);
+
+    std::copy(sorted.begin(), sorted.end(), rotated.begin());
+    std::rotate(rotated.begin(), rotated.begin() + 1, rotated.end());
+
+    evaluateRawArray(randomizedArray, sorted, reversed, organPipe, rotated);
+    evaluateStdArray(randomizedArray, sorted, reversed, organPipe, rotated);
+    evaluateStdVector(randomizedArray, sorted, reversed, organPipe, rotated);
+
+    return 0;
+}
diff --git a/Homework/cs3460/array_perf/sortutils.cpp b/Homework/cs3460/array_perf/sortutils.cpp
new file mode 100644
index 0000000..402f561
--- /dev/null
+++ b/Homework/cs3460/array_perf/sortutils.cpp
@@ -0,0 +1,238 @@
+#include "sortutils.hpp"
+
+/**
+ * @struct SortResult stores simple information about a sorting time result
+ */
+struct SortResult
+{
+    std::string title;
+    std::uint64_t duration;
+};
+
+/**
+ * @param std::string sequentialString: use "Sequential" or "Parallel"
+ * @param std::vector<struct SortResult>: the list of results from a sorting run
+ * @return void: format all the sorting results according to program requirements
+ */
+void formatSortResults(std::string sequentialString, const std::vector<struct SortResult>& results)
+{
+    const std::string timeStr = " Time";
+    std::uint32_t longestTitle = static_cast<std::uint32_t>(std::max_element(
+                                                                results.begin(),
+                                                                results.end(),
+                                                                [](const struct SortResult s1, const struct SortResult s2) { return s1.title.length() < s2.title.length(); })
+                                                                ->title.length());
+    std::cout << sequentialString << std::endl;
+    for (auto sortResult : results)
+    {
+        std::cout << fmt::format("\t{0:<{1}} : {2} ms", sortResult.title + timeStr, longestTitle + timeStr.length(), sortResult.duration)
+                  << std::endl;
+    }
+    std::cout << std::endl;
+}
+
+/**
+ * @param std::string title: title of the array type used
+ * @param std::vector<struct SortResult> sequentialResults: list of results of sequential sorts
+ * @param std::vector<struct SortResult> parallelResults: list of results of parallel sorts
+ * @return void: format the results and title according to program requirements
+ */
+void formatArrayTypeSortResults(std::string title, const std::vector<struct SortResult>& sequentialResults, const std::vector<struct SortResult>& parallelResults)
+{
+    std::cout << fmt::format("  --- {0} Performance ---", title) << std::endl;
+    formatSortResults("Sequential", sequentialResults);
+    formatSortResults("Parallel", parallelResults);
+}
+
+/**
+ * @param SourceArray source: source array to copy into->
+ * @param int[] dest: the raw array to copy source's elements to
+ * @return void: do the copy
+ */
+void initializeRawArrayFromStdArray(const SourceArray& source, int dest[])
+{
+    std::copy(std::execution::par, source.begin(), source.end(), dest);
+}
+
+/**
+ * @param SourceArray data: the source data to convert into a "organ pipe" array per program requirements
+ * @return void: do the piping
+ */
+void organPipeStdArray(SourceArray& data)
+{
+    float mid = HOW_MANY_ELEMENTS / 2.0;
+    std::reverse_copy(std::execution::par, data.begin(), data.begin() + static_cast<std::uint32_t>(std::floor(mid)), data.begin() + static_cast<std::uint32_t>(std::ceil(mid)));
+}
+
+/**
+ * @param function<void()> func: the function to time
+ * @return uint64_t: the milliseconds required to execute func()
+ */
+std::uint64_t executionMs(std::function<void()> func)
+{
+    std::chrono::time_point start = std::chrono::steady_clock::now();
+    func();
+    return std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start).count();
+}
+
+/**
+ * @param SourceArray source: the values to copy into rawArray HOW_MANY_TIMES times
+ * @param int[] rawArray: the raw array to benchmark
+ * @param bool parallel: whether to use parallel execution
+ * @return uint64_t: time (in ms) to sort copied values from source -> rawArray HOW_MANY_TIMES times
+ */
+std::uint64_t totalTimeToSortRawArrayManyTimes(const SourceArray& source, int rawArray[], bool parallel)
+{
+    std::uint64_t ms = 0;
+    for (std::uint32_t i = 0; i < HOW_MANY_TIMES; i++)
+    {
+        initializeRawArrayFromStdArray(source, rawArray);
+        if (parallel)
+        {
+            ms += executionMs([&rawArray]() -> void { std::sort(std::execution::par_unseq, rawArray, rawArray + HOW_MANY_ELEMENTS); });
+        }
+        else
+        {
+            ms += executionMs([&rawArray]() -> void { std::sort(std::execution::seq, rawArray, rawArray + HOW_MANY_ELEMENTS); });
+        }
+    }
+    return ms;
+}
+
+/**
+ * @param SourceArray source: the values to copy into rawArray HOW_MANY_TIMES times
+ * @param SourceArray stdArray: the std::array to benchmark
+ * @param bool parallel: whether to use parallel execution
+ * @return uint64_t: time (in ms) to sort copied values from source -> stdArray HOW_MANY_TIMES times
+ */
+std::uint64_t totalTimeToSortStdArrayManyTimes(const SourceArray& source, SourceArray& stdArray, bool parallel)
+{
+    std::uint64_t ms = 0;
+    for (std::uint32_t i = 0; i < HOW_MANY_TIMES; i++)
+    {
+        std::copy(source.begin(), source.end(), stdArray.begin());
+        if (parallel)
+        {
+            ms += executionMs([&stdArray]() -> void { std::sort(std::execution::par_unseq, stdArray.begin(), stdArray.end()); });
+        }
+        else
+        {
+            ms += executionMs([&stdArray]() -> void { std::sort(std::execution::seq, stdArray.begin(), stdArray.end()); });
+        }
+    }
+    return ms;
+}
+
+/**
+ * @param SourceArray source: the values to copy into rawArray HOW_MANY_TIMES times
+ * @param SourceArray stdVector: the vector to benchmark
+ * @param bool parallel: whether to use parallel execution
+ * @return uint64_t: time (in ms) to sort copied values from source -> stdVector HOW_MANY_TIMES times
+ */
+std::uint64_t totalTimeToSortStdVectorManyTimes(const SourceArray& source, std::vector<int>& stdVector, bool parallel)
+{
+    std::uint64_t ms = 0;
+    for (std::uint32_t i = 0; i < HOW_MANY_TIMES; i++)
+    {
+        std::copy(source.begin(), source.end(), stdVector.begin());
+        if (parallel)
+        {
+            ms += executionMs([&stdVector]() -> void { std::sort(std::execution::par_unseq, stdVector.begin(), stdVector.end()); });
+        }
+        else
+        {
+            ms += executionMs([&stdVector]() -> void { std::sort(std::execution::seq, stdVector.begin(), stdVector.end()); });
+        }
+    }
+    return ms;
+}
+
+/**
+ * @param SourceArray random: a list of random values initialize in main.cpp
+ * @param SourceArray sorted: random, but sorted in sequential order
+ * @param SourceArray reversed: sorted, but reversed
+ * @param SourceArray organPipe: sorted, but "organ-piped"
+ * @param SourceArray rotated: sorted, but rotated by one
+ * @return void: format results of the raw array benchmark
+ */
+void evaluateRawArray(const SourceArray& random, const SourceArray& sorted, const SourceArray& reversed, const SourceArray& organPipe, const SourceArray& rotated)
+{
+    int rawArray[HOW_MANY_ELEMENTS];
+    std::vector<struct SortResult> seqResults{
+        { "Random", totalTimeToSortRawArrayManyTimes(random, rawArray, false) },
+        { "Sorted", totalTimeToSortRawArrayManyTimes(sorted, rawArray, false) },
+        { "Reversed", totalTimeToSortRawArrayManyTimes(reversed, rawArray, false) },
+        { "Organ Piped", totalTimeToSortRawArrayManyTimes(organPipe, rawArray, false) },
+        { "Rotated", totalTimeToSortRawArrayManyTimes(rotated, rawArray, false) },
+    };
+
+    std::vector<struct SortResult> parResults{
+        { "Random", totalTimeToSortRawArrayManyTimes(random, rawArray, true) },
+        { "Sorted", totalTimeToSortRawArrayManyTimes(sorted, rawArray, true) },
+        { "Reversed", totalTimeToSortRawArrayManyTimes(reversed, rawArray, true) },
+        { "Organ Piped", totalTimeToSortRawArrayManyTimes(organPipe, rawArray, true) },
+        { "Rotated", totalTimeToSortRawArrayManyTimes(rotated, rawArray, true) },
+    };
+
+    formatArrayTypeSortResults("Raw Array", seqResults, parResults);
+}
+
+/**
+ * @param SourceArray random: a list of random values initialize in main.cpp
+ * @param SourceArray sorted: random, but sorted in sequential order
+ * @param SourceArray reversed: sorted, but reversed
+ * @param SourceArray organPipe: sorted, but "organ-piped"
+ * @param SourceArray rotated: sorted, but rotated by one
+ * @return void: format results of the std array benchmark
+ */
+void evaluateStdArray(const SourceArray& random, const SourceArray& sorted, const SourceArray& reversed, const SourceArray& organPipe, const SourceArray& rotated)
+{
+    SourceArray stdArray;
+    std::vector<struct SortResult> seqResults{
+        { "Random", totalTimeToSortStdArrayManyTimes(random, stdArray, false) },
+        { "Sorted", totalTimeToSortStdArrayManyTimes(sorted, stdArray, false) },
+        { "Reversed", totalTimeToSortStdArrayManyTimes(reversed, stdArray, false) },
+        { "Organ Piped", totalTimeToSortStdArrayManyTimes(organPipe, stdArray, false) },
+        { "Rotated", totalTimeToSortStdArrayManyTimes(rotated, stdArray, false) },
+    };
+
+    std::vector<struct SortResult> parResults{
+        { "Random", totalTimeToSortStdArrayManyTimes(random, stdArray, true) },
+        { "Sorted", totalTimeToSortStdArrayManyTimes(sorted, stdArray, true) },
+        { "Reversed", totalTimeToSortStdArrayManyTimes(reversed, stdArray, true) },
+        { "Organ Piped", totalTimeToSortStdArrayManyTimes(organPipe, stdArray, true) },
+        { "Rotated", totalTimeToSortStdArrayManyTimes(rotated, stdArray, true) },
+    };
+
+    formatArrayTypeSortResults("std::array", seqResults, parResults);
+}
+
+/**
+ * @param SourceArray random: a list of random values initialize in main.cpp
+ * @param SourceArray sorted: random, but sorted in sequential order
+ * @param SourceArray reversed: sorted, but reversed
+ * @param SourceArray organPipe: sorted, but "organ-piped"
+ * @param SourceArray rotated: sorted, but rotated by one
+ * @return void: format results of the std vector benchmark
+ */
+void evaluateStdVector(const SourceArray& random, const SourceArray& sorted, const SourceArray& reversed, const SourceArray& organPipe, const SourceArray& rotated)
+{
+    std::vector<int> stdVector(HOW_MANY_ELEMENTS);
+    std::vector<struct SortResult> seqResults{
+        { "Random", totalTimeToSortStdVectorManyTimes(random, stdVector, false) },
+        { "Sorted", totalTimeToSortStdVectorManyTimes(sorted, stdVector, false) },
+        { "Reversed", totalTimeToSortStdVectorManyTimes(reversed, stdVector, false) },
+        { "Organ Piped", totalTimeToSortStdVectorManyTimes(organPipe, stdVector, false) },
+        { "Rotated", totalTimeToSortStdVectorManyTimes(rotated, stdVector, false) },
+    };
+
+    std::vector<struct SortResult> parResults{
+        { "Random", totalTimeToSortStdVectorManyTimes(random, stdVector, true) },
+        { "Sorted", totalTimeToSortStdVectorManyTimes(sorted, stdVector, true) },
+        { "Reversed", totalTimeToSortStdVectorManyTimes(reversed, stdVector, true) },
+        { "Organ Piped", totalTimeToSortStdVectorManyTimes(organPipe, stdVector, true) },
+        { "Rotated", totalTimeToSortStdVectorManyTimes(rotated, stdVector, true) },
+    };
+
+    formatArrayTypeSortResults("std::vector", seqResults, parResults);
+}
diff --git a/Homework/cs3460/array_perf/sortutils.hpp b/Homework/cs3460/array_perf/sortutils.hpp
new file mode 100644
index 0000000..202ca4e
--- /dev/null
+++ b/Homework/cs3460/array_perf/sortutils.hpp
@@ -0,0 +1,36 @@
+#ifndef SORTUTILS_HPP
+#define SORTUTILS_HPP
+
+#include <algorithm>
+#include <array>
+#include <chrono>
+#include <cmath>
+#include <cstdint>
+#include <execution>
+#include <functional>
+#include <iostream>
+#include <random>
+#if defined(_MSC_VER)
+    #pragma warning(push)
+    #pragma warning(disable : 4189) // Disable some compiler warnings that come from fmt
+#endif
+#include <fmt/std.h>
+#if defined(_MSC_VER)
+    #pragma warning(pop)
+#endif
+
+const std::size_t HOW_MANY_ELEMENTS = 250000;
+const std::uint8_t HOW_MANY_TIMES = 25;
+using SourceArray = std::array<int, HOW_MANY_ELEMENTS>;
+
+void initializeRawArrayFromStdArray(const SourceArray& source, int dest[]);
+
+void organPipeStdArray(SourceArray& data);
+
+void evaluateRawArray(const SourceArray& random, const SourceArray& sorted, const SourceArray& reversed, const SourceArray& organPipe, const SourceArray& rotated);
+
+void evaluateStdArray(const SourceArray& random, const SourceArray& sorted, const SourceArray& reversed, const SourceArray& organPipe, const SourceArray& rotated);
+
+void evaluateStdVector(const SourceArray& random, const SourceArray& sorted, const SourceArray& reversed, const SourceArray& organPipe, const SourceArray& rotated);
+
+#endif // SORTUTILS_HPP