C#での整数の割り算の速度などを調べてみました。
元は、Utf8Jsonのソースコードです。C言語のころから、itoaとか言うのがあるらしいです。
intなどの整数の値が、0 <= n <10000 の時、それを桁で分解する方法で、速い方法があるとのこと。
1の位と、10以上の位に分割するときのケースですが、
例) n:1234 → a:123 , b:4
普通に行うと、
a = n / 10;
b = n - a * 10;
となります。
bの部分については、
b = n % 10;このように、 % を使うことでも可能ですが、わかりやすくはなりますが、遅くなります。
%演算が遅いのは、割り算を行っているのが一つ。
また、intなど負の数が扱える時は、%演算の結果も負になるので、そこらも原因かと推測します
-12 % 10 = -2さて、10で割るコードを、割らない、以下の書き方でも実行できます。
a = (n * 6554) >> 16;
b = n - a * 10;掛け算とシフト演算に置き換えるそうです。
割り算というやつは、どうにも時間がかかる様で、掛け算とシフト演算の2命令になっても、こちらの方が速いみたいです。
さて、結果が本当に正しいかと、どのくらい速度差があるのかについて、確認してみました。
シフト演算など使っているので、どの整数の型でも正しく動作するのかちょっと心配だったんですね。
確認する型は、int,uint,long,ulong です。shortとかは調べてません。
調べる対象は、/10 以外にも、/100 , /1000 も検証しました。
/100のケースは、
a = (n * 5243) >> 19;
b = n - a * 100;/1000のケースは、
a = (value * 8389) >> 23;
b = value - a * 1000;テストコードの掲載は割愛しますが、各型で、0～9999の値でのループを行い、通常の割り算と乗算＋シフト演算で同じ結果になることを確認しました。
どの型でも問題なく同じ結果になり、安心しました。
さて、速度計測ですが、こちらは、最後にコードを掲載しておきます。ちょっと長いですが。
まず結果です。
//| Method | Mean | Error | StdDev |
//|----------------------- |---------:|----------:|----------:|
//| Div10IntBench | 7.246 us | 0.0276 us | 0.0258 us |
//| Div100IntBench | 7.246 us | 0.0308 us | 0.0288 us |
//| Div1000IntBench | 7.254 us | 0.0327 us | 0.0290 us |
//| PowShift10IntBench | 4.841 us | 0.0780 us | 0.0730 us |
//| PowShift100IntBench | 4.891 us | 0.0313 us | 0.0292 us |
//| PowShift1000IntBench | 4.885 us | 0.0231 us | 0.0216 us |
//| Div10LongBench | 7.344 us | 0.0277 us | 0.0231 us |
//| Div100LongBench | 7.942 us | 0.0145 us | 0.0113 us |
//| Div1000LongBench | 7.362 us | 0.0238 us | 0.0199 us |
//| PowShift10LongBench | 4.863 us | 0.0389 us | 0.0364 us |
//| PowShift100LongBench | 4.874 us | 0.0595 us | 0.0557 us |
//| PowShift1000LongBench | 4.897 us | 0.0364 us | 0.0340 us |
//| Div10UIntBench | 4.664 us | 0.0371 us | 0.0347 us |
//| Div100UIntBench | 4.362 us | 0.0133 us | 0.0111 us |
//| Div1000UIntBench | 4.357 us | 0.0157 us | 0.0139 us |
//| PowShift10UIntBench | 4.921 us | 0.0108 us | 0.0101 us |
//| PowShift100UIntBench | 4.914 us | 0.0136 us | 0.0128 us |
//| PowShift1000UIntBench | 4.868 us | 0.0541 us | 0.0506 us |
//| Div10ULongBench | 6.053 us | 0.0274 us | 0.0256 us |
//| Div100ULongBench | 6.931 us | 0.0101 us | 0.0094 us |
//| Div1000ULongBench | 6.930 us | 0.0155 us | 0.0130 us |
//| PowShift10ULongBench | 4.871 us | 0.0429 us | 0.0401 us |
//| PowShift100ULongBench | 4.841 us | 0.0540 us | 0.0479 us |
//| PowShift1000ULongBench | 4.859 us | 0.0287 us | 0.0268 us |置き換え効果の高い順に、long → int → ulong → uint となります。
uintに限っては、なんと遅くなってしまいました。
CPU依存とかもあるかもしれないので書いておきますと、私の環境は、
CPU:Ryzen5 3600(6-Core)
.Net7.0.400
です。
やはり、桁数が大きくなると、割り算が大変になって、あと、負数を扱える型の方が、割り算が遅くなる様です。
いちど、絶対値を外して処理するなどの実装が入っているのではないかと推測します。
さて、最後にベンチマークのコードを書いておきます。
public class DivBenchTarget
{
// int
[Benchmark]
public int Div10IntBench()
{
int sum = 0;
for (int i = 0; i < 10000; i++)
{
sum += i / 10;
}
return sum;
}
[Benchmark]
public int Div100IntBench()
{
int sum = 0;
for (int i = 0; i < 10000; i++)
{
sum += i / 100;
}
return sum;
}
[Benchmark]
public int Div1000IntBench()
{
int sum = 0;
for (int i = 0; i < 10000; i++)
{
sum += i / 1000;
}
return sum;
}
[Benchmark]
public int PowShift10IntBench()
{
int sum = 0;
for (int i = 0; i < 10000; i++)
{
sum += (i * 6554) >> 16;
}
return sum;
}
[Benchmark]
public int PowShift100IntBench()
{
int sum = 0;
for (int i = 0; i < 10000; i++)
{
sum += (i * 5243) >> 19;
}
return sum;
}
[Benchmark]
public int PowShift1000IntBench()
{
int sum = 0;
for (int i = 0; i < 10000; i++)
{
sum += (i * 8389) >> 23;
}
return sum;
}
// long
[Benchmark]
public long Div10LongBench()
{
long sum = 0;
for (long i = 0; i < 10000; i++)
{
sum += i / 10;
}
return sum;
}
[Benchmark]
public long Div100LongBench()
{
long sum = 0;
for (long i = 0; i < 10000; i++)
{
sum += i / 100;
}
return sum;
}
[Benchmark]
public long Div1000LongBench()
{
long sum = 0;
for (long i = 0; i < 10000; i++)
{
sum += i / 1000;
}
return sum;
}
[Benchmark]
public long PowShift10LongBench()
{
long sum = 0;
for (long i = 0; i < 10000; i++)
{
sum += (i * 6554) >> 16;
}
return sum;
}
[Benchmark]
public long PowShift100LongBench()
{
long sum = 0;
for (long i = 0; i < 10000; i++)
{
sum += (i * 5243) >> 19;
}
return sum;
}
[Benchmark]
public long PowShift1000LongBench()
{
long sum = 0;
for (long i = 0; i < 10000; i++)
{
sum += (i * 8389) >> 23;
}
return sum;
}
// uint
[Benchmark]
public uint Div10UIntBench()
{
uint sum = 0;
for (uint i = 0; i < 10000; i++)
{
sum += i / 10;
}
return sum;
}
[Benchmark]
public uint Div100UIntBench()
{
uint sum = 0;
for (uint i = 0; i < 10000; i++)
{
sum += i / 100;
}
return sum;
}
[Benchmark]
public uint Div1000UIntBench()
{
uint sum = 0;
for (uint i = 0; i < 10000; i++)
{
sum += i / 1000;
}
return sum;
}
[Benchmark]
public uint PowShift10UIntBench()
{
uint sum = 0;
for (uint i = 0; i < 10000; i++)
{
sum += (i * 6554) >> 16;
}
return sum;
}
[Benchmark]
public uint PowShift100UIntBench()
{
uint sum = 0;
for (uint i = 0; i < 10000; i++)
{
sum += (i * 5243) >> 19;
}
return sum;
}
[Benchmark]
public uint PowShift1000UIntBench()
{
uint sum = 0;
for (uint i = 0; i < 10000; i++)
{
sum += (i * 8389) >> 23;
}
return sum;
}
// ulong
[Benchmark]
public ulong Div10ULongBench()
{
ulong sum = 0;
for (ulong i = 0; i < 10000; i++)
{
sum += i / 10;
}
return sum;
}
[Benchmark]
public ulong Div100ULongBench()
{
ulong sum = 0;
for (ulong i = 0; i < 10000; i++)
{
sum += i / 100;
}
return sum;
}
[Benchmark]
public ulong Div1000ULongBench()
{
ulong sum = 0;
for (ulong i = 0; i < 10000; i++)
{
sum += i / 1000;
}
return sum;
}
[Benchmark]
public ulong PowShift10ULongBench()
{
ulong sum = 0;
for (ulong i = 0; i < 10000; i++)
{
sum += (i * 6554) >> 16;
}
return sum;
}
[Benchmark]
public ulong PowShift100ULongBench()
{
ulong sum = 0;
for (ulong i = 0; i < 10000; i++)
{
sum += (i * 5243) >> 19;
}
return sum;
}
[Benchmark]
public ulong PowShift1000ULongBench()
{
ulong sum = 0;
for (ulong i = 0; i < 10000; i++)
{
sum += (i * 8389) >> 23;
}
return sum;
}
}