大型数组或列表的4桶直方图的微优化

Question

我有一个特殊问题。我将尽力描述这一点。

我正在做一个非常重要的“微观优化”。一次运行几天的循环。因此，如果我可以减少此循环时间，则只需花费一半的时间。 10天将减少到只有5天，等等。

我现在拥有的循环是函数：“ testbenchmark1”。

我有4个索引，需要像这样在循环中增加。但是，当我从列表中访问索引时，实际上需要花费一些额外的时间。如果没有其他解决方案，这就是我要尝试的方法。

indexes[n]++; //increase correct index

“ testbenchmark1”的完整代码，需要122毫秒：

void testbenchmark00()
{
    Random random = new Random();
    List<int> indexers = new List<int>();
    for (int i = 0; i < 9256408; i++)
    {
        indexers.Add(random.Next(0, 4));
    }
    int[] valueLIST = indexers.ToArray();


    Stopwatch stopWatch = new Stopwatch();
    stopWatch.Start();

    int[] indexes = { 0, 0, 0, 0 };
    foreach (int n in valueLIST) //Takes 122 ms
    {
        indexes[n]++; //increase correct index
    }

    stopWatch.Stop();
    MessageBox.Show("stopWatch: " + stopWatch.ElapsedMilliseconds.ToString() + " milliseconds");
}

现在下面的“ testbenchmark2”代码只是实验性的，我知道它是不正确的，但是我想知道是否有任何类似的方法可以使用此类数字：“ 1_00_00_00_00”，并且是否有可能看到：“ 00_00_00_00” ”作为四个不同的整数。例如，如果我将求和：1_00_00_00_00 + 1_00_01_00_00 = 1_00_01_00_00，然后最后可以提取每个数字，则四个这样的每个数字：00、01、00、00

但是我不知道即使使用二进制数也不能以任何方式做到这一点。是的，任何解决方案。只是这样添加数字。就像测试一样，循环仅花费59毫秒，是122毫秒的一半。因此，我很感兴趣看看是否有任何想法吗？

double num3 = 1_00_00_00_00;
double num4 = 1_00_01_00_00;
for (int i = 0; i < valueLIST.Count; i++) //Takes 59 ms
{
    num3 += num4;
}

“ testbenchmark2”的完整代码，耗时59毫秒：

void testbenchmark2()
{
    List<String> valueLIST = new List<String>(); 
    for (int i = 0; i < 9256408; i++) //56
    {
        valueLIST.Add(i.ToString());
    }

    //https://www.geeksforgeeks.org/binary-literals-and-digit-separators-in-c-sharp/
    double num3 = 1_00_00_00_00;
    double num4 = 1_00_01_00_00;

    Stopwatch stopWatch = new Stopwatch();
    stopWatch.Start();
    for (int i = 0; i < valueLIST.Count; i++) //Takes 59 ms
    {
        num3 += num4;
    }
    stopWatch.Stop();
    MessageBox.Show("stopWatch: " + stopWatch.ElapsedMilliseconds.ToString() + " milliseconds\n\n" + num3);
}

编辑下面是我正在尝试做的更干净的代码！但是下面的代码可能是正确的或解决方案，但它表明了我想做的事情。

        void newtest()
        {
            double num1 = 1_00_00_00_00;
            double num2 = 1_00_01_00_00;
            double num3 = 1_00_01_01_00;

            List<double> testnumbers = new List<double>();
            testnumbers.Add(num1);
            testnumbers.Add(num2);
            testnumbers.Add(num3);

            double SUM = 0;
            for (int i = 0; i < testnumbers.Count; i++)
            {
                SUM += testnumbers[i];
            }

            //The result is
            //300020100

            //Would it possible to extract the "four buckets" that I am interesting in somehow?
            //00_02_01_00
        }

Answer 1

如Peter Cordes所述，您可以使用SIMD一次将多个值加在一起，请参见vector。但是我不清楚这是否真的有帮助。

编辑：如果您正在运行.Net核心，则还有SIMD intrinstics可提供对硬件的较低级别访问。

如NerualHandle所述，使用for循环比使用foreach更好。但是，当我对其进行测试时，似乎没有显着差异。我想编译器可以在这种特殊情况下优化foreach。

[当我运行您的testbenchmark00代码时，它将在〜6ms的计算机上完成。一些粗略的计算表明，循环的每次迭代大约需要0.78ns，或大约2-4个处理器周期，这似乎是最佳的。花费您大约20倍的时间似乎很奇怪。您是否正在发布模式下运行？

您可以并行解决问题。将indexers数组拆分为多个部分，并在不同的线程上构建每个部分的直方图，最后对每个线程的直方图求和。 See Parallel.For因为这可以为您完成分区等操作，但是它需要使用localInit和localFinally来确保每个线程将数据写入单独的直方图中，以避免并发问题。

与性能优化一样，推荐的操作顺序是：

1. 用于识别问题区域的配置文件代码
2. 寻找算法上的改进
3. 寻找减少工作量的方法，例如缓存
4. 更快地完成现有工作