c# convert string to decimal integer i.e. 100

cpp10

DDD888 发表于 21-8-2013 16:35

                               
登录/注册后可看大图

Maybe you post your c code and let me test under visual studio 2013.

root@ubuntu:~/test# gcc -DSYS x.cc ; time ./a.out 100000000

real    0m0.438s
user    0m0.436s
sys     0m0.004s
root@ubuntu:~/test# gcc -DM x.cc ; time ./a.out 100000000

real    0m9.694s
user    0m9.673s
sys     0m0.004s
root@ubuntu:~/test# gcc x.cc ; time ./a.out 100000000

real    0m10.256s
user    0m10.205s
sys     0m0.016s
root@ubuntu:~/test# cat x.cc
#include <stdlib.h>

#ifdef SYS
#define ATOI atoi
#else
#define ATOI atoi_
#endif

using namespace std;
int atoi_(const char* p)
{
  int result = 0;
  while(*p)
  {
#ifdef M
    result = result*10 + *p++ - '0' ;
#else
        switch(*p++)
        {
                case '0': result = result*10 ; break;
                case '1': result = result*10 + 1 ; break;
                case '2': result = result*10 + 2 ; break;
                case '3': result = result*10 + 3 ; break;
                case '4': result = result*10 + 4 ; break;
                case '5': result = result*10 + 5 ; break;
                case '6': result = result*10 + 6 ; break;
                case '7': result = result*10 + 7 ; break;
                case '8': result = result*10 + 8 ; break;
                case '9': result = result*10 + 9 ; break;
                default: break;
        }
#endif
  }

  return result;
}

int _atoi(const char *s)
{
        unsigned int i=0,n;

        for(n = 0; s; i++) n = 10 * n + s - '0';

        return n;
}

int main(int argc, char* argv[])
{
        int loop = atoi(argv[1]);

        for(int i=0; i<loop; i++)
                ATOI("1234567890");

        return 0;
}
root@ubuntu:~/test#

superopengl

刚做了实验：
1000万个随即数字字符串（全是0-9的字符）
楼主的unsafe switch算法： 1880 millionseconds
result += value - 48算法：2672 millionseconds
Convert.ToInt32算法：1735 millionseconds

10万个随即数字字符串（全是0-9的字符）
楼主的unsafe switch算法： 19 millionseconds
result += value - 48算法：27 millionseconds
Convert.ToInt32算法：18 millionseconds

结果上看，Convert.ToInt32是最快的。这个结果可以理解，一般的字符转数字，不会有比framework更好的算法。我怀疑楼主的bottleneck不是integer parsing，而是全文string scanning提取数字的部分。建议使用Regex match数字，然后用Convert.ToInt32转换。

通常情况下不要怀疑.NET的基本算法，那都是一堆精英写出来的，在基础算法方面，几乎不可能有优化的余地了。

DDD888

superopengl 发表于 21-8-2013 18:10

                               
登录/注册后可看大图

刚做了实验：
1000万个随即数字字符串（全是0-9的字符）
楼主的unsafe switch算法： 1880 millionseconds ...

You are right.

I think that I extracted the string which cause memory allocation and slow down performance. I was using profiler and saw my code cut 0.8 seconds out of 5 seconds for the whole process instead of Convert.ToInt32. As I said before, I remove the convert to int routine from the code.

DDD888

cpp10 发表于 21-8-2013 17:45

                               
登录/注册后可看大图

root@ubuntu:~/test# gcc -DSYS x.cc ; time ./a.out 100000000

real    0m0.438s

Your result on linux is really odd.

I am compiling with default configuration release mode.

If #define M 1
Time spent 766ms

comment out #define M 1
Time spent 782ms

use system routine atoi
Time spent 4454ms

It was running on a i3 cpu.

Here is your code I modified under visual studio

#include "stdafx.h"

//#define M 1
int
atoi_(const char* p)
{
        int result = 0;
        while(*p)
        {
#ifdef M
                result = result*10 + *p++ - '0' ;
#else
        switch(*p++)
        {
                case '0': result = result*10 ; break;
                case '1': result = result*10 + 1 ; break;
                case '2': result = result*10 + 2 ; break;
                case '3': result = result*10 + 3 ; break;
                case '4': result = result*10 + 4 ; break;
                case '5': result = result*10 + 5 ; break;
                case '6': result = result*10 + 6 ; break;
                case '7': result = result*10 + 7 ; break;
                case '8': result = result*10 + 8 ; break;
                case '9': result = result*10 + 9 ; break;
                default: break;
        }
#endif
        }

  return result;
}

int _tmain(int argc, _TCHAR* argv[])
{
        int loop = _ttoi(argv[1]);

        int ntime=0;
        LARGE_INTEGER ntime1,ntime2;
        LARGE_INTEGER freq;
        QueryPerformanceFrequency(&freq);
        QueryPerformanceCounter(&ntime1);

        int result;
    for (int i = 0; i < loop; i++)
        {
//                result = atoi_("1234567890");
                result = atoi("1234567890");
        }

        QueryPerformanceCounter(&ntime2);
        //get ntime in millisecs
        ntime = (ntime2.QuadPart-ntime1.QuadPart)/(freq.QuadPart/1000);
        printf("Time spent %d\r\n", ntime);

    return 0;
}

cpp10

DDD888 发表于 21-8-2013 19:16

                               
登录/注册后可看大图

Your result on linux is really odd.

I am compiling with default configuration release mode.

PS D:\test> start-process cl.exe -ArgumentList "/D SYS c.cpp"
PS D:\test> Measure-Command {Start-Process c.exe -ArgumentList "100000000" -wait
}


Days              : 0
Hours             : 0
Minutes           : 0
Seconds           : 6
Milliseconds      : 124
Ticks             : 61249506
TotalDays         : 7.08906319444444E-05
TotalHours        : 0.00170137516666667
TotalMinutes      : 0.10208251
TotalSeconds      : 6.1249506
TotalMilliseconds : 6124.9506

PS D:\test> start-process cl.exe -ArgumentList "/D M c.cpp"
PS D:\test> Measure-Command {Start-Process c.exe -ArgumentList "100000000" -wait
}


Days              : 0
Hours             : 0
Minutes           : 0
Seconds           : 3
Milliseconds      : 561
Ticks             : 35617250
TotalDays         : 4.12236689814815E-05
TotalHours        : 0.000989368055555556
TotalMinutes      : 0.0593620833333333
TotalSeconds      : 3.561725
TotalMilliseconds : 3561.725

PS D:\test> start-process cl.exe -ArgumentList "c.cpp"
PS D:\test> Measure-Command {Start-Process c.exe -ArgumentList "100000000" -wait
}


Days              : 0
Hours             : 0
Minutes           : 0
Seconds           : 6
Milliseconds      : 391
Ticks             : 63919657
TotalDays         : 7.39810844907407E-05
TotalHours        : 0.00177554602777778
TotalMinutes      : 0.106532761666667
TotalSeconds      : 6.3919657
TotalMilliseconds : 6391.9657

workinvm

superopengl 发表于 21-8-2013 16:53

                               
登录/注册后可看大图

我也看过关于“C#的switch编译后是以hashtable形式存在”的一本书，但我的经验这个说法对于C#来讲是不正 ...

被你说糊涂了，我刚刚用 VS2012 做了一个简单的 switch 试了一下
1. debug 时是直接跳到 matched case的。
2. 你那个语句根本编译不通过，C#根本不允许这样写， case 1 后面必须加 break 或者 case 1 case 2 连在一起。
请问你是自己想当然的，还是确实有这种情况？你用的什么版本的 .net 和 什么版本的 virtual studio?

superopengl

workinvm 发表于 21-8-2013 21:13

                               
登录/注册后可看大图

被你说糊涂了，我刚刚用 VS2012 做了一个简单的 switch 试了一下
1. debug 时是直接跳到 matched case的 ...

1. debug的断点在case里面吧。按照MSDN，关于C#的switch的解释
“Execution of the statement list in the selected section begins with the first statement and proceeds through the statement list, typically until a jump statement is reached, such as a break, goto case, return, or throw. ”

2. Sorry, 我的例子不对，那个是C++语法的。谢谢纠正。

superopengl

刚才反编译了一下下面的C#代码，发现编译器(2.0和4.0结果一样)编译出的是if-else。
原code
public static int SwitchSample(string str)
{
    var x = 0;
    switch (str)
    {
        case "a":
        case "b":
            x = 1;
            break;
        case "c":
            x = 2;
            break;
    }
    return x;
}

反编译出的code（by ILSpy）
public static int SwitchSample(string str)
{
        int x = 0;
        if (str != null)
        {
                if (!(str == "a") && !(str == "b"))
                {
                        if (str == "c")
                        {
                                x = 2;
                        }
                }
                else
                {
                        x = 1;
                }
        }
        return x;
}

workinvm

superopengl 发表于 22-8-2013 09:58

                               
登录/注册后可看大图

1. debug的断点在case里面吧。按照MSDN，关于C#的switch的解释
“Execution of the statement list in t ...

1. debug 的断点是在 case 里面，但不是像你理解的那样是从 case 1 开始一个一个执行到断点的。
你贴的那段英文的意思是说在选择的段（case 段）中执行语句是从第一个语句开始顺序执行直到遇到跳转语句。并不能理解为是从第一个case 段开始顺序执行。
2. 本来我想说你是 C++ 语法，但你又写了个 Console.Writeline 这样的 C# 语句，而不是 print 这样的C++ 打印语句，所以我就糊涂了，呵呵。
你应该是 C++ / C#程序员吧？我现在也同时在搞 C++  和 C#,同行啊，握个手

xychar

to 楼主： 能满足需要就可以了，要那么快干嘛？
如果真想快，还是拿 ansi c 来写吧，很多牛逼的高性能软件都是拿这个写的

superopengl

看了一下IL code, 进一步修正调查结果：
1. 对于switch case integer， 对于有序case，编译成switch(jump table)，无序case编译为if-else。根据case值的不同，有时直接跳到matched case，有时if-else
2. 对于小规模switch case string （小于等于6个case），编译成if-else
3. 对于大规模switch case string （7个及7个case以上）, 先生成一个Dictionary<string, int>，然后紧跟一个switch(jump table)指令，直接跳到matched case。

应该说，switch的效率并不高，而且行为无法预测（比如1000个乱序的case interger来说，生成1000个以上的if-else）。编制基础算法的时候应该尽量回避。

superopengl

cpp10 发表于 11-8-2013 09:00

                               
登录/注册后可看大图

switch执行很慢的、result += (x-'0') 会快很多

#include

You are right. The Convert.Int32 was written internally like "result += x - 48;".
But it's odd that this algorithm got the worst result in my investigation. Maybe my code was not good enough.

Another thing is that, I used to said "minus operation is slower than plus", that's not quite true. To computer, minus operation is actually plus operation with a reverse operation. So it should not be that slow in contrast with plus.

DDD888

xychar 发表于 22-8-2013 10:37

                               
登录/注册后可看大图

to 楼主： 能满足需要就可以了，要那么快干嘛？
如果真想快，还是拿 ansi c 来写吧，很多牛逼的高性能软件 ...

If always profile the code to write the fastest code, my guess is the time spent running .net code is close enough to ansi c on Windows.

superopengl

workinvm 发表于 22-8-2013 09:25

                               
登录/注册后可看大图

1. debug 的断点是在 case 里面，但不是像你理解的那样是从 case 1 开始一个一个执行到断点的。
你贴的那 ...

我想是因为switch有时是jump table的行为，有时是if-else的行为，所以MSDN为了保险起见（也免得解释具体细节），才写着从第一个开始依次执行。而且描述的很模糊。（如果是if-else行为，实际上并不是按照原C# code的顺序执行的，而是IL code的conditional顺序。对于jump table行为，则直接到matched case，不存在顺序的问题。）
“Execution of the statement list in the selected section begins with the first statement and proceeds through the statement list, typically until a jump statement is reached, such as a break, goto case, return, or throw. ”

workinvm

superopengl 发表于 22-8-2013 11:29

                               
登录/注册后可看大图

我想是因为switch有时是jump table的行为，有时是if-else的行为，所以MSDN为了保险起见（也免得解释具体细 ...

英文写的很清楚，不是很模糊，你看这段
Execution of the statement list in the selected section
这个从句中有个 in the selected section 这个地方限制了前面讲的 Execution of the statement 是在 the selected section 里面的，即 matched case 里面的，而不是你理解的从第一个 case 开始顺序执行。
我附上中文版本 MSDN 官方翻译的这段话，以帮助你理解
语句体从选定的语句开始执行，直到 break 将控制传递到 case 体以外。在每一个 case 块（包括上一个块，不论它是 case 语句还是 default 语句）的后面，都必须有一个跳转语句（如 break）。但有一个例外，（与 C++ switch 语句不同）C# 不支持从一个 case 标签显式贯穿到另一个 case 标签。这个例外是当 case 语句中没有代码时。

workinvm

superopengl 发表于 22-8-2013 11:14

                               
登录/注册后可看大图

看了一下IL code, 进一步修正调查结果：
1. 对于switch case integer， 对于有序case，编译成switch(jump  ...

小于 6 个情况下 if - else 比 Hash 要快，所以编译器这样优化的估计。
1000 个乱序的 case interge 生产 1000 个 if - else 是你看 IL code 得出的吗？
其实选择用 C# 就要考虑牺牲一定性能的， C# 最大的问题是 GC 的回收无法控制。而且代码是在运行时才动态编译成机器目标代码的，这些特性对于要求高性能，高实时性的系统来说都是灾难性的。
歪楼了，楼主的问题我认为是其他原因造成的。

superopengl

workinvm 发表于 22-8-2013 11:58

                               
登录/注册后可看大图

小于 6 个情况下 if - else 比 Hash 要快，所以编译器这样优化的估计。
1000 个乱序的 case interge 生产 ...

> 1000 个乱序的 case interge 生产 1000 个 if - else 是你看 IL code 得出的吗？
You are right. IL code shows me that.