ASCII到uint16使用ASCII

Question

Introduction

看着这次谈话，我想我可以把它应用到解析较小的数字上，比如std::uint16_t。不过，我使用了一条using直通开关语句对其进行了扩展。基本上，它从std::string_view的后面开始，然后一直沿着std::string_view的起点下降。

constexpr std::uint16_t atou16(const std::string_view s)
{
    auto first = s.crbegin();
    std::uint16_t result = 0;
    constexpr std::uint16_t powers[] = {1, 10, 100, 1'000, 10'000};

    const std::size_t size = s.size();
    switch (size)
    {
        case 5:
            result += powers[4] * (first[4] - '0');
        case 4:
            result += powers[3] * (first[3] - '0');
        case 3:
            result += powers[2] * (first[2] - '0');
        case 2:
            result += powers[1] * (first[1] - '0');
        case 1:
            result += powers[0] * (first[0] - '0');
        default:
            ;
    }

    return result;
}

基线

基线实现是传统的乘以10的循环。

constexpr std::uint16_t simple_atou16(const std::string_view s)
{
    auto first = s.cbegin();
    std::uint16_t result = 0;
    while (first != s.cend())
    {
        result = static_cast<std::uint16_t>(result * 10)
                 + static_cast<std::uint16_t>(*first++ - '0');
    }

    return result;
}

时间

时间显示，在简单的情况下，解析器的新版本确实更快。

不过，由于字符串长度的关系，运行时不是线性的，这让我有点困扰。我相信在某些情况下也会发生溢出，因为std::uint16_t并不涵盖所有5位数字。不过，我对此视而不见，因为这是基准本身的问题。

我一直在做一些正常的事情，比如在后台播放youtube上的音乐，所以我认为这应该是相当大的负担。我考虑过生成虚拟线程，这会带来更多的负载，但无法决定哪个更合适。

全码

atou16.cpp

#include <string_view>
#include <cstdint>

constexpr std::uint16_t simple_atou16(const std::string_view s)
{
    auto first = s.cbegin();
    std::uint16_t result = 0;
    while (first != s.cend())
    {
        result = static_cast<std::uint16_t>(result * 10)
                 + static_cast<std::uint16_t>(*first++ - '0');
    }

    return result;
}

constexpr std::uint16_t atou16(const std::string_view s)
{
    auto first = s.crbegin();
    std::uint16_t result = 0;
    constexpr std::uint16_t powers[] = {1, 10, 100, 1'000, 10'000};

    const std::size_t size = s.size();
    switch (size)
    {
        case 5:
            result += powers[4] * (first[4] - '0');
        case 4:
            result += powers[3] * (first[3] - '0');
        case 3:
            result += powers[2] * (first[2] - '0');
        case 2:
            result += powers[1] * (first[1] - '0');
        case 1:
            result += powers[0] * (first[0] - '0');
        default:
            ;
    }

    return result;
}

#include <random>
#include <algorithm>

std::string generate_random_number(unsigned int digits)
{
    static std::mt19937 twister{};
    static std::uniform_int_distribution<char> distribution{'1', '9'};

    std::string number(digits, '\0');
    auto generator = [&](){return distribution(twister);};
    std::generate(number.begin(), number.end(), generator);

    return number;
}

#include <iostream>
#include <atomic>
#include <chrono>
#include <fstream>
#include <vector>

long run_test(unsigned int digits, unsigned int runcount)
{
    std::vector<std::uint16_t> values(runcount);
    std::vector<std::string> numbers(runcount);
    auto generator = [digits](){return generate_random_number(digits);};
    std::generate(numbers.begin(), numbers.end(), generator);

    using namespace std::chrono;
    auto start = high_resolution_clock::now();
    std::atomic_thread_fence(std::memory_order_seq_cst);
    for (unsigned int i = 0; i < runcount; ++i)
    {
        values[i] = atou16(numbers[i]);
    }
    std::atomic_thread_fence(std::memory_order_seq_cst);
    auto end = high_resolution_clock::now();

    for (auto x: values)
        std::cout << x << '\n';

    std::cout << '\n';

    return duration_cast<microseconds>(end - start).count();
}

long run_test_simple(unsigned int digits, unsigned int runcount)
{
    std::vector<std::uint16_t> values(runcount);
    std::vector<std::string> numbers(runcount);
    auto generator = [digits](){return generate_random_number(digits);};
    std::generate(numbers.begin(), numbers.end(), generator);

    using namespace std::chrono;
    auto start = high_resolution_clock::now();
    std::atomic_thread_fence(std::memory_order_seq_cst);
    for (unsigned int i = 0; i < runcount; ++i)
    {
        values[i] = simple_atou16(numbers[i]);
    }
    std::atomic_thread_fence(std::memory_order_seq_cst);
    auto end = high_resolution_clock::now();

    for (auto x: values)
        std::cout << x << '\n';

    std::cout << '\n';
    return duration_cast<microseconds>(end - start).count();
}

int main(int argc, char* argv[])
{
    if (argc != 2)
    {
        std::cerr << "usage: atou16 <output-file-csv>\n";
        return 1;
    }

    std::ofstream timings_out{argv[1]};
    if (!timings_out)
    {
        std::cerr << "output file opening failed\n";
        return 1;
    }

    timings_out << "\"digit count\",fallthrough,simple\n";
    for (unsigned int digits = 2; digits < 6; ++digits)
    {
        timings_out << digits << ','
                    << run_test(digits, 1'000'000) << ','
                    << run_test_simple(digits, 1'000'000) << '\n';
    }
}

CMakeLists.txt

cmake_minimum_required(VERSION 3.2)
project(atou16)

set(CMAKE_CXX_STANDARD 17)

if (NOT CMAKE_BUILD_TYPE)
    set(CMAKE_BUILD_TYPE Release)
endif()

if(CMAKE_BUILD_TYPE EQUAL "Release")
    set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -O3 -march=native")
endif()

add_executable(atou16 atou16.cpp)

plotter.py

#!/usr/bin/python3

import matplotlib.pyplot as plt
import csv
import argparse
import sys

parser = argparse.ArgumentParser()
parser.add_argument('csv_filename', help='file which contains data to plot from')
parser.add_argument('--noshow', action='store_true', help="don't show resulting plot")
parser.add_argument('--nosave', action='store_true', help="don't save resulting plot")
args = parser.parse_args()

labels = []
x = []
fallthrough_y = []
simple_y = []

with open(args.csv_filename, 'r') as csvfile:
    plots = csv.reader(csvfile, delimiter=',')
    labels_row = next(plots)
    labels.append(labels_row[0])
    labels.append(labels_row[1])
    labels.append(labels_row[2])

    for row in plots:
        x.append(int(row[0]))
        fallthrough_y.append(int(row[1]))
        simple_y.append(int(row[2]))

fig = plt.figure('ASCII to uint16 timings')
plt.locator_params(axis='x', nbins = 4)
plt.plot(x, fallthrough_y, label=labels[1])
plt.plot(x, simple_y, label=labels[2])

plt.xlabel(labels[0])
plt.ylabel('microseconds')

plt.legend()

if not args.nosave:
    fig.savefig('plot.png')

if not args.noshow:
    plt.show();

关注

• 基准精度我能做些什么来消除背景噪音吗？
• Powers表表可能占用CPU寄存器中宝贵的空间。也许它可以用某种方式包装？
• 基准方法是否正确？
• 这里还有任何代码。我知道python脚本很可怕。

Answer 1

将每个数字乘以不同的幂，其乘法次数与将每个部分和乘以10相乘的次数相同。但是，如果您看一下生成的代码，我在这个职位 (参见函数decode)中发现，乘10是用两个简单的指令完成的:乘5是通过寻址生成器端口通过LEA RAX,[RAX+4*RAX]缩放索引加起来的，索引和偏移量是相同的寄存器；然后用类似的技巧将2乘到+=中。

乘各种其他值可能不会使用这样的技巧，但需要常规的MUL指令或更长的添加序列。

我发现的另一件事(在那篇文章中)是，使用16位ints是最慢的！对于某些16位操作，x86特别慢。使用32或64 (在x64构建中)是最快的。因此，我建议简单地更改数据类型并再次运行计时，看看会发生什么。

我还发现(请参阅这个职位)，对于相同长度的签名和无符号操作，有些操作的速度不同。同时，我看到演示文稿展示了如何在没有签名的情况下生成更糟的代码，而没有优化的空间更小。因此，探索不同的类型和图表的结果。

您的展开循环，就像通常的方式一样，具有运行中的依赖关系。每一行都要求在添加前一行之前完成。

我已经成功地并行运行了两次计算，方法是将问题分解，然后在最后将它们组合起来。因此，将两个不同的和交叉起来，并在链的末尾将它们加在一起。

编译器将自行展开循环。

switch语句将导致糟糕的分支预测，并且(正如引用的文章中所指出的)是性能的杀手。

如果你能用SIMD并行地做所有的乘法，那就太酷了。用10的幂加载一个YMM寄存器，用数字加载另一个。