CityStatsTask.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <sys/types.h>
#include <algorithm>
#include <atomic>
#include <chrono>
#include <iostream>
#include <ostream>
#include <ratio>
#include <semaphore>
#include <sstream>
#include <string>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <fstream>
#include <cstring>
#include <cstdint>
#include <cassert>
using namespace std::chrono_literals;


int64_t operator""_kb(unsigned long long value) {
    return value * 1024;
}

int64_t operator""_mb(unsigned long long value) {
    return value * (1024 * 1024);
}

int64_t operator""_gb(unsigned long long value) {
    return value * (1024 * 1024 * 1024);
}

/// Allocate aligned for @count objects of type T, does not perform initialization
/// @param count - the number of objects
/// @param unaligned [out] - stores the un-aligned pointer, used to call free
/// @return pointer to the memory or nullptr
template <typename T>
T *alignedAlloc(size_t count, void *&unaligned) {
    const size_t bytes = count * sizeof(T);
    unaligned = malloc(bytes + 63);
    if (!unaligned) {
        return nullptr;
    }
    T *const aligned = reinterpret_cast<T *>(uintptr_t(unaligned) + 63 & -64);
    return aligned;
}

/// Stack allocator with predefined max size
/// The total memory is 64 byte aligned, all but the first allocation are not guaranteed to be algigned
/// Can only free all the allocations at once
struct StackAllocator {
    StackAllocator(uint8_t *ptr, int64_t bytes)
        : totalBytes(bytes)
        , data(ptr) {
    }

    /// Allocate memory for @count T objects
    /// Does *NOT* call constructors
    /// @param count - the number of objects needed
    /// @return pointer to the allocated memory or nullptr
    template <typename T>
    T *alloc(int64_t count) {
        const int64_t size = count * sizeof(T);
        if (idx + size > totalBytes) {
            return nullptr;
        }
        uint8_t *start = data + idx;
        idx += size;
        return reinterpret_cast<T *>(start);
    }

    /// De-allocate all the memory previously allocated with @alloc
    void freeAll() {
        idx = 0;
    }

    /// Get the max number of bytes that can be allocated by the allocator
    int64_t maxBytes() const {
        return totalBytes;
    }

    /// Get the free space that can still be allocated, same as maxBytes before any allocations
    int64_t freeBytes() const {
        return totalBytes - idx;
    }

    void zeroAll() const {
        memset(data, 0, totalBytes);
    }

    StackAllocator(const StackAllocator &) = delete;
    StackAllocator &operator=(const StackAllocator &) = delete;
private:
    const int64_t totalBytes;
    int64_t idx = 0;
    uint8_t *data = nullptr;
};

void ThrashCache() {
    static std::vector<uint8_t> trash(100_mb);
    std::atomic_thread_fence(std::memory_order_acq_rel);
    volatile uint8_t *data = trash.data();
    for (int c = 0; c < 10; c++) {
        for (int i = 0; i < int(trash.size()); i++) {
            data[i] = data[i] * 2 + 1;
        }
    }
    std::atomic_thread_fence(std::memory_order_acq_rel);
}


/**
 * Interface for the city stats
 * The city stats are used to store information about cities
 * The cities have an id, name, direction, temperature and humidity
 * The direction is one of the following: north, south, east, west, north-east, north-west, south-east, south-west
 * The temperature is a floating point number
 * The humidity is a floating point number
 * The city stats can be loaded from a file, updated with commands and saved to a file
 */
struct CityStatsInterface {
    StackAllocator *allocator = nullptr;
    CityStatsInterface(StackAllocator *allocator) : allocator(allocator) {}
    virtual void LoadFromFile(std::istream &in) = 0;
    virtual void ExecuteCommands(std::istream &commands) = 0;
    virtual void SaveData(std::ostream &temperature, std::ostream &humidity, std::ostream &directions) = 0;
};

const int MAX_CITY_NAME_LEN = 31;

struct CityInfo {
    int64_t id = -1;
    char name[MAX_CITY_NAME_LEN + 1]{};
    char direction[16]{};
    float temperature{};
    float humidity{};
};

float RoundFloat(float value) {
    return float(int(value * 10) / 10.0);
}

/**
 * CityStats implementation
 * Sample implementation of the CityStatsInterface
 */
struct CityStats : CityStatsInterface {
    std::vector<CityInfo> data;
    std::unordered_map<std::string, std::string> leftRotatedDir, rightRotatedDir;

    CityStats(StackAllocator *allocator) : CityStatsInterface(allocator) {
        leftRotatedDir["north"] = "north-west";
        leftRotatedDir["north-west"] = "west";
        leftRotatedDir["west"] = "south-west";
        leftRotatedDir["south-west"] = "south";
        leftRotatedDir["south"] = "south-east";
        leftRotatedDir["south-east"] = "east";
        leftRotatedDir["east"] = "north-east";
        leftRotatedDir["north-east"] = "north";

        rightRotatedDir["north"] = "north-east";
        rightRotatedDir["north-east"] = "east";
        rightRotatedDir["east"] = "south-east";
        rightRotatedDir["south-east"] = "south";
        rightRotatedDir["south"] = "south-west";
        rightRotatedDir["south-west"] = "west";
        rightRotatedDir["west"] = "north-west";
        rightRotatedDir["north-west"] = "north";
    }

    void LoadFromFile(std::istream &in) override {
        CityInfo city;
        while (in >> city.id >> city.name >> city.direction >> city.temperature >> city.humidity) {
            data.push_back(city);
        }
    }

    virtual void ExecuteCommands(std::istream &commands) override {
        char type;
        int64_t from, to;
        float delta;
        char rotate;
        while (commands >> type >> from >> to >> delta >> rotate) {
            if (type == 't') {
                UpdateTemperatureInRange(from, to, delta, rotate);
            } else {
                UpdateHumidityInRange(from, to, delta, rotate);
            }
        }
    }

    void UpdateTemperatureInRange(int64_t startID, int64_t endID, float delta, char rotate) {
        auto start = std::lower_bound(data.begin(), data.end(), startID, [](const CityInfo &city, int64_t id) {
            return city.id < id;
        });
        auto end = std::upper_bound(data.begin(), data.end(), endID, [](int64_t id, const CityInfo &city) {
            return id < city.id;
        });

        for (auto it = start; it != end; ++it) {
            if (rotate == 'r') {
                strcpy(it->direction, rightRotatedDir[it->direction].c_str());
            } else {
                strcpy(it->direction, leftRotatedDir[it->direction].c_str());
            }
            it->temperature += delta;
        }
    }

    void UpdateHumidityInRange(int64_t startID, int64_t endID, float delta, char rotate) {
        auto start = std::lower_bound(data.begin(), data.end(), startID, [](const CityInfo &city, int64_t id) {
            return city.id < id;
        });
        auto end = std::upper_bound(data.begin(), data.end(), endID, [](int64_t id, const CityInfo &city) {
            return id < city.id;
        });

        for (auto it = start; it != end; ++it) {
            if (rotate == 'r') {
                strcpy(it->direction, rightRotatedDir[it->direction].c_str());
            } else {
                strcpy(it->direction, leftRotatedDir[it->direction].c_str());
            }
            it->humidity += delta;
            if (it->humidity < 0) {
                it->humidity = 0;
            } else if (it->humidity > 100) {
                it->humidity = 100;
            }
        }
    }

    virtual void SaveData(std::ostream &temperature, std::ostream &humidity, std::ostream &directions) override {
        float sumTemp = 0;
        float sumHumidity = 0;
        std::unordered_map<std::string, int> dirCount;
        for (const auto &city : data) {
            sumTemp += city.temperature;
            sumHumidity += city.humidity;
            dirCount[city.direction]++;
            temperature.write(reinterpret_cast<const char *>(&city.temperature), sizeof(float));
            humidity.write(reinterpret_cast<const char *>(&city.humidity), sizeof(float));
            directions << city.direction << ' ';
        }
        const float avgHumidity = float(int(sumHumidity / data.size()));
        const float avgTemperature = float(int(sumTemp / data.size()));

        temperature.write(reinterpret_cast<const char *>(&avgTemperature), sizeof(float));
        humidity.write(reinterpret_cast<const char *>(&avgHumidity), sizeof(float));

        std::string mostCommonDir = dirCount.begin()->first;
        for (const auto &dir : dirCount) {
            if (dir.second > dirCount[mostCommonDir]) {
                mostCommonDir = dir.first;
            }
        }
        directions << mostCommonDir << ' ';
    }
};

struct TestDescription {
    int cityCount;
    int64_t itemCount;
    int64_t updateCount;
    std::string name;
    int repeat = 10;
};

struct DataGenerator {
    std::vector<std::string> cities;
    std::vector<std::string> directions = { "north", "south", "east", "west", "north-east", "north-west", "south-east", "south-west" };
    std::mt19937_64 rng{ 0xdeadbeef };

    DataGenerator() {
    }

    void GenerateData(const TestDescription &desc) {
        cities.clear();
        GenerateRandomCities(desc.cityCount);
        int64_t start, end;
        GenerateCityData(desc.name, desc.itemCount, start, end);
        GenerateUpdateCommands(desc.name, desc.updateCount, start, end);
    }

    static void GenerateTestData(const std::vector<TestDescription> &tests) {
        DataGenerator gen;
        for (const auto &desc : tests) {
            std::cout << "Generating data for test " << desc.name << std::endl;
            gen.GenerateData(desc);
        }
    }

    void GenerateUpdateCommands(const std::string &name, int64_t count, int64_t startID, int64_t endID) {
        std::uniform_int_distribution<int64_t> id(startID, endID);
        std::uniform_real_distribution<float> delta(-10, 10);
        std::uniform_int_distribution<int> typePicker(0, 1);
        char rotateDir[2] = { 'r', 'l' };
        char type[2] = { 't', 'h' };

        std::ofstream out(name + "-updates.txt", std::ios::binary);
        for (int64_t c = 0; c < count; c++) {
            const int64_t a = id(rng);
            const int64_t b = id(rng);
            out << type[typePicker(rng)] << ' ' << std::min(a, b) << ' ' << std::max(a, b) << ' ' << RoundFloat(delta(rng)) << ' ' << rotateDir[typePicker(rng)] << '\n';
        }
    }

    void GenerateCityData(const std::string &name, int64_t count, int64_t &startID, int64_t &endID) {
        std::uniform_int_distribution<int> cityPicker(0, int(cities.size() - 1));
        std::uniform_int_distribution<int> idSkip(1, 10);
        std::normal_distribution<float> temperature(20, 10);
        std::uniform_real_distribution<float> humidity(0, 100);
        std::uniform_int_distribution<int> directionPicker(0, int(directions.size() - 1));

        std::ofstream out(name + "-cities.txt", std::ios::binary);
        startID = idSkip(rng);
        for (int64_t c = 0, id = startID; c < count; c++) {
            out << id << ' ' << cities[cityPicker(rng)] << ' ' << directions[directionPicker(rng)] << ' ' << RoundFloat(temperature(rng)) << ' ' << RoundFloat(humidity(rng)) << '\n';
            id += idSkip(rng);
            endID = id;
        }
    }

    void GenerateRandomCities(int count) {
        cities.resize(count);
        std::uniform_int_distribution<int> letter('a', 'z');
        std::uniform_int_distribution<int> cityLen(4, MAX_CITY_NAME_LEN);
        std::generate(cities.begin(), cities.end(), [this, &letter, &cityLen]() {
            std::string city;
            const int len = cityLen(rng);
            for (int i = 0; i < len; ++i) {
                city.push_back(letter(rng));
            }
            return city;
        });
    }
};

struct Tester {
    CityStatsInterface *base;
    CityStatsInterface *update;
    bool timeTester;
    Tester(CityStatsInterface *base, CityStatsInterface *update, bool timeTester) : base(base), update(update), timeTester(timeTester) {}

    struct TestResult {
        bool correct{ false };
        struct Times {
            std::chrono::nanoseconds loadTime{};
            std::chrono::nanoseconds commandsTime{};
            std::chrono::nanoseconds saveTime{};
        };
        Times base;
        Times update;
    };

    TestResult RunTest(const std::string &name) {
        std::vector<float> baseData;
        std::vector<float> updateData;
        std::string baseDir, updateDir;
        TestResult result;

        if (timeTester) {
            ThrashCache();
        }
        result.base = TestImplementation(name, base, baseData, baseDir, "base");
        if (timeTester) {
            ThrashCache();
        }
        result.update = TestImplementation(name, update, updateData, updateDir, "update");

        if (!timeTester) {
            result.correct = FindDiffInData(baseData, updateData) == -1;
            if (baseDir != updateDir) {
                std::cout << "Different directions: [" << baseDir << ']' << std::endl << std::endl << '[' << updateDir << ']' << std::endl;
                result.correct = false;
            }
        }

        return result;
    }

    template <typename Function>
    static std::chrono::nanoseconds TestFunction(Function &&f) {
        auto start = std::chrono::high_resolution_clock::now();
        std::atomic_thread_fence(std::memory_order_acq_rel);
        f();
        std::atomic_thread_fence(std::memory_order_acq_rel);
        return std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now() - start);
    }

    static TestResult::Times TestImplementation(const std::string &name, CityStatsInterface *test, std::vector<float> &data, std::string &directionsOut, const std::string &type) {
        std::ifstream in(name + "-cities.txt", std::ios::binary);
        std::ifstream commands(name + "-updates.txt", std::ios::binary);
        TestResult::Times res;

        res.loadTime = TestFunction([&]() {
            test->LoadFromFile(in);
        });

        res.commandsTime = TestFunction([&]() {
            test->ExecuteCommands(commands);
        });

        std::stringstream temperature;
        std::stringstream humidity;
        std::stringstream directions;
        res.saveTime = TestFunction([&]() {
            test->SaveData(temperature, humidity, directions);
        });

        directionsOut = directions.str();
        const int64_t tempSize = temperature.tellp() / sizeof(float);
        const int64_t humSize = humidity.tellp() / sizeof(float);
        temperature.seekg(0);
        humidity.seekg(0);

        data.resize(tempSize + humSize);
        temperature.read(reinterpret_cast<char *>(data.data()), tempSize * sizeof(float));
        humidity.read(reinterpret_cast<char *>(data.data() + tempSize), humSize * sizeof(float));

        return res;
    }

    int64_t FindDiffInData(const std::vector<float> &a, const std::vector<float> &b) {
        if (a.size() != b.size()) {
            std::cout << "Difference in size " << a.size() << " " << b.size() << std::endl;
            return -2;
        }
        int64_t diff = -1;
        for (int64_t c = 0; c < int64_t(a.size()); c++) {
            if (a[c] != b[c]) {
                std::cout << "Difference at " << c << " " << a[c] << " " << b[c] << std::endl;
                if (diff == -1) {
                    diff = c;
                }
            }
        }
        return diff;
    }
};

std::ostream &PrintTime(std::ostream &out, const std::chrono::nanoseconds &ns) {
    auto us = std::chrono::duration_cast<std::chrono::microseconds>(ns);
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(ns);
    auto s = std::chrono::duration_cast<std::chrono::seconds>(ns);
    if (s > 10s) {
        return out << s;
    } else if (ms > 10ms) {
        return out << ms;
    } else if (us > 10us) {
        return out << us;
    } else {
        return out << ns;
    }
}

std::ostream &operator<<(std::ostream &out, const Tester::TestResult::Times &times) {
    PrintTime(out, times.loadTime) << ' ';
    PrintTime(out, times.commandsTime) << ' ';
    PrintTime(out, times.saveTime);
    return out;
}

const int repeat = 5;
std::vector<TestDescription> tests = {
    {3, 1000, 10, "small", repeat},
    {100, 10'000, 10'000, "medium", repeat},
    {100, 50'000, 20'000, "large", repeat},
    {100, 1'000, 1'000'000, "many-updates", repeat},
    {1000, 10'000'000, 100, "many-records", repeat},
    {100'000, 1'000'000, 100, "many-cities", repeat},
};

//////////////////////// BEGIN IMPLEMENTATION ////////////////////////
// No changes outside of this region are allowed
// Implement the FastCityStats class here
using FastCityStats = CityStats;
//////////////////////// END IMPLEMENTATION ////////////////////////

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


    StackAllocator empty(nullptr, 0);
    StackAllocator allocator(new uint8_t[1_gb], 1_gb);

    if (argc == 2) {
        if (strcmp(argv[1], "generate") == 0) {
            DataGenerator::GenerateTestData(tests);
        } else if (strcmp(argv[1], "check") == 0) {
            for (const auto &desc : tests) {
                CityStats base(&empty);
                FastCityStats update(&allocator);
                Tester test(&base, &update, false);
                std::cout << "Results for: \"" << desc.name << "\":" << std::endl;
                const auto res = test.RunTest(desc.name);
                if (res.correct) {
                    std::cout << "- Correct" << std::endl;
                } else {
                    std::cout << "- Incorrect" << std::endl;
                }
            }
        } else if (std::isdigit(argv[1][0])) {
            const int idx = atoi(argv[1]);
            if (idx < 0 || idx >= int(tests.size())) {
                std::cout << "Invalid test index\n";
                return 1;
            }
            std::vector<Tester::TestResult::Times> res;
            res.reserve(repeat);
            std::vector<float> data;
            std::string output;
            std::cout << "Running test " << tests[idx].name << " " << repeat << " times\n";
            for (int c = 0; c < repeat; c++) {
                allocator.freeAll();
                FastCityStats update(&allocator);
                const auto times = Tester::TestImplementation(tests[idx].name, &update, data, output, "update");
                res.push_back(times);
            }
            for (const auto &time : res) {
                std::cout << time << std::endl;
            }
        } else if (!strcmp(argv[1], "help")) {
            std::cout << "Usage: CityInfo [command]\n";
            std::cout << "Commands:\n";
            std::cout << "  generate - generate test data\n";
            std::cout << "  check - check the correctness of the implementation\n";
            std::cout << "  [index] - run a single test\n";
            std::cout << "  <no-args> - run all timing tests\n";
        } else {
            std::cout << "Unknown command\n";
        }
        return 0;
    }

    std::shuffle(tests.begin(), tests.end(), std::mt19937_64(std::random_device()()));

    for (const auto &desc : tests) {
        std::cout << "Results for " << desc.name << std::endl;
        std::cout << "base(load, commands, save) | update(load, commands, save)" << std::endl;
        const int repeatCount = desc.repeat;
        std::vector<Tester::TestResult::Times> baseResults, updateResults;
        for (int c = 0; c < repeatCount; c++) {
            allocator.zeroAll();
            allocator.freeAll();
            CityStats base(&empty);
            FastCityStats update(&allocator);
            Tester test(&base, &update, true);
            const auto res = test.RunTest(desc.name);
            baseResults.push_back(res.base);
            updateResults.push_back(res.update);
            std::cout << baseResults[c] << " | ";
            std::cout << updateResults[c] << std::endl;
        }
        int bestBase = 0, bestUpdate = 0;
        std::chrono::nanoseconds totalBase{}, totalUpdate{};
        for (int c = 0; c < int(baseResults.size()); c++) {
            const auto baseTime = baseResults[c].loadTime + baseResults[c].commandsTime + baseResults[c].saveTime;
            const auto updateTime = updateResults[c].loadTime + updateResults[c].commandsTime + updateResults[c].saveTime;
            totalBase += baseTime;
            totalUpdate += updateTime;
            if (baseTime < baseResults[bestBase].loadTime + baseResults[bestBase].commandsTime + baseResults[bestBase].saveTime) {
                bestBase = c;
            }
            if (updateTime < updateResults[bestUpdate].loadTime + updateResults[bestUpdate].commandsTime + updateResults[bestUpdate].saveTime) {
                bestUpdate = c;
            }
        }
        std::cout << "Average base: ";
        PrintTime(std::cout, totalBase / repeatCount) << " Average update: ";
        PrintTime(std::cout, totalUpdate / repeatCount) << std::endl;
        std::cout << "Best base: " << baseResults[bestBase] << " Best update: " << updateResults[bestUpdate] << std::endl;
        std::cout << std::endl;
        std::cout << "Best load speedup: " << float(baseResults[bestBase].loadTime.count()) / updateResults[bestUpdate].loadTime.count() << "x\n";
        std::cout << "Best commands speedup: " << float(baseResults[bestBase].commandsTime.count()) / updateResults[bestUpdate].commandsTime.count() << "x\n";
        std::cout << "Best save speedup: " << float(baseResults[bestBase].saveTime.count()) / updateResults[bestUpdate].saveTime.count() << "x\n";
        std::cout << std::endl;
        const float speedup = float(totalBase.count()) / totalUpdate.count();
        std::cout << "Total Speedup: " << speedup << "x\n";
        std::cout << "----------------------------------------\n";
    }

    return 0;
}