你如何使这个 switch 语句尽可能快? [英] How would you make this switch statement as fast as possible?

问题描述

2009-12-04 更新:有关此处发布的一些建议的分析结果，请参见下文！

2009-12-04 UPDATE: For profiling results on a number of the suggestions posted here, see below!

考虑以下非常无害、非常直接的方法，它使用 switch 语句返回定义的枚举值:

Consider the following very harmless, very straightforward method, which uses a switch statement to return a defined enum value:

public static MarketDataExchange GetMarketDataExchange(string ActivCode) {
    if (ActivCode == null) return MarketDataExchange.NONE;

    switch (ActivCode) {
        case "": return MarketDataExchange.NBBO;
        case "A": return MarketDataExchange.AMEX;
        case "B": return MarketDataExchange.BSE;
        case "BT": return MarketDataExchange.BATS;
        case "C": return MarketDataExchange.NSE;
        case "MW": return MarketDataExchange.CHX;
        case "N": return MarketDataExchange.NYSE;
        case "PA": return MarketDataExchange.ARCA;
        case "Q": return MarketDataExchange.NASDAQ;
        case "QD": return MarketDataExchange.NASDAQ_ADF;
        case "W": return MarketDataExchange.CBOE;
        case "X": return MarketDataExchange.PHLX;
        case "Y": return MarketDataExchange.DIRECTEDGE;
    }

    return MarketDataExchange.NONE;
}

我和我的同事今天讨论了一些关于如何真正使这种方法更快的想法，我们提出了一些有趣的修改，这些修改实际上确实显着提高了它的性能(当然，按比例来说).我很想知道其他人能想到哪些我们可能没有想到的优化.

My colleague and I batted around a few ideas today about how to actually make this method faster, and we came up with some interesting modifications that did in fact improve its performance rather significantly (proportionally speaking, of course). I'd be interested to know what sorts of optimizations anyone else out there can think up that might not have occurred to us.

马上，让我提供一个简短的免责声明:这是为了有趣，不是推动整个优化还是不优化"辩论.也就是说，如果您认为自己属于那些教条主义地相信过早的优化是万恶之源"的人，请注意我在一家高频交易公司工作，一切都需要绝对运行尽可能快——瓶颈与否.所以，即使我在 SO 上发布这个是为了乐趣，这也不仅仅是浪费时间.

Right off the bat, let me just offer a quick disclaimer: this is for fun, and not to fuel the whole "to optimize or not to optimize" debate. That said, if you count yourself among those who dogmatically believe "premature optimization is the root of all evil," just be aware that I work for a high-frequency trading firm, where everything needs to run absolutely as fast as possible--bottleneck or not. So, even though I'm posting this on SO for fun, it isn't just a huge waste of time, either.

另一个快速说明:我对两种答案感兴趣 - 假设每个输入都是有效的 ActivCode(上面的 switch 语句中的字符串之一)，以及那些那不.我几乎确信做出第一个假设可以进一步提高速度；无论如何，它为我们做了.但我知道无论哪种方式都可以改进.

One more quick note: I'm interested in two kinds of answers--those that assume every input will be a valid ActivCode (one of the strings in the switch statement above), and those that do not. I am almost certain that making the first assumption allows for further speed improvements; anyway, it did for us. But I know that improvements are possible either way.

嗯，事实证明，迄今为止(我测试过的)最快的解决方案来自 João Angelo，他的建议实际上非常简单，但非常聪明.我和我的同事设计的解决方案(在尝试了几种方法之后，其中许多也是在这里想到的)排在第二位.我正要发布它，但事实证明 Mark Ransom 提出了完全相同的想法，所以请查看他的答案！

Well, it turns out that the fastest solution so far (that I've tested) came from João Angelo, whose suggestion was actually very simple, yet extremely clever. The solution that my coworker and I had devised (after trying out several approaches, many of which were thought up here as well) came in second place; I was going to post it, but it turns out that Mark Ransom came up with the exact same idea, so just check out his answer!

自从我运行这些测试后，其他一些用户发布了甚至更新的想法...我会在适当的时候测试它们，当我有更多的空闲时间时.

Since I ran these tests, some other users have posted even newer ideas... I will test them in due time, when I have a few more minutes to spare.

我在两台不同的机器上运行了这些测试:我家的个人电脑(一台运行 Windows 7 64 位、4 Gb RAM 的双核 Athlon)和我工作的开发机器(一台 2 Gb RAM 的双核 Athlon运行 Windows XP SP3).显然，时代不同了.但是，相对时间，意思是每种方法与其他方法相比的方式是相同的.也就是说，最快的是两台机器上最快的等等.

I ran these tests on two different machines: my personal computer at home (a dual-core Athlon with 4 Gb RAM running Windows 7 64-bit) and my development machine at work (a dual-core Athlon with 2 Gb RAM running Windows XP SP3). Obviously, the times were different; however, the relative times, meaning, how each method compared to every other method, were the same. That is to say, the fastest was the fastest on both machines, etc.

现在来看结果.(我在下面发布的时间来自我的家用电脑.)

Now for the results. (The times I'm posting below are from my home computer.)

但首先，作为参考——原始 switch 语句:
1000000 次运行:98.88 毫秒
平均:0.09888 微秒

But first, for reference--the original switch statement:
1000000 runs: 98.88 ms
Average: 0.09888 microsecond

迄今为止最快的优化:

1. João Angelo 的想法是基于 ActivCode 字符串的哈希码为枚举分配值，然后直接将 ActivCode.GetHashCode() 封装为 MarketDataExchange:
   1000000 次运行:23.64 毫秒
   平均:0.02364 微秒
   速度提升:329.90%

1. João Angelo's idea of assigning values to the enums based on the hash codes of the ActivCode strings and then directly casing ActivCode.GetHashCode() to MarketDataExchange:
   1000000 runs: 23.64 ms
   Average: 0.02364 microsecond
   Speed increase: 329.90%

我的同事和我将 ActivCode[0] 转换为 int 并从初始化的数组中检索适当的 MarketDataExchange 的想法在启动时(Mark Ransom 提出了完全相同的想法):
1000000 次运行:28.76 毫秒
平均:0.02876 微秒
速度提升:253.13%

My colleague's and my idea of casting ActivCode[0] to an int and retrieving the appropriate MarketDataExchange from an array initialized on startup (this exact same idea was suggested by Mark Ransom):
1000000 runs: 28.76 ms
Average: 0.02876 microsecond
Speed increase: 253.13%

tster 开启 ActivCode.GetHashCode() 输出而不是 ActivCode 的想法:
1000000 次运行:34.69 毫秒
平均:0.03469 微秒
速度提升:185.04%

tster's idea of switching on the output of ActivCode.GetHashCode() instead of ActivCode:
1000000 runs: 34.69 ms
Average: 0.03469 microsecond
Speed increase: 185.04%

由包括 Auraseer、tster 和 kyoryu 在内的几位用户提出的建议是使用 ActivCode[0] 而不是 ActivCode:
1000000 次运行:36.57 毫秒
平均:0.03657 微秒
速度提升:174.66%

The idea, suggested by several users including Auraseer, tster, and kyoryu, of switching on ActivCode[0] instead of ActivCode:
1000000 runs: 36.57 ms
Average: 0.03657 microsecond
Speed increase: 174.66%

Loadmaster 使用快速哈希的想法，ActivCode[0] + ActivCode[1]*0x100:
1000000 次运行:39.53 毫秒
平均:0.03953 微秒
速度提升:153.53%

Loadmaster's idea of using the fast hash, ActivCode[0] + ActivCode[1]*0x100:
1000000 runs: 39.53 ms
Average: 0.03953 microsecond
Speed increase: 153.53%

许多人建议使用散列表(Dictionary):
1000000 次运行:88.32 毫秒
平均:0.08832 微秒
速度提升:12.36%

Using a hashtable (Dictionary<string, MarketDataExchange>), as suggested by many:
1000000 runs: 88.32 ms
Average: 0.08832 microsecond
Speed increase: 12.36%

使用二分查找:
1000000 次运行:1031 毫秒
平均:1.031 微秒
速度提升:无(性能变差)

Using a binary search:
1000000 runs: 1031 ms
Average: 1.031 microseconds
Speed increase: none (performance worsened)

我只想说，看到人们对这个简单的问题有多少不同的想法，真是太酷了.这对我来说非常有趣，我非常感谢迄今为止做出贡献和提出建议的每个人.

Let me just say that it has been really cool to see how many different ideas people had on this simple problem. This was very interesting to me, and I'm quite thankful to everyone who has contributed and made a suggestion so far.

推荐答案

假设每一个输入都是一个有效的ActivCode，你可以改变枚举值并与GetHashCode<高度耦合/code> 实现:

Assuming every input will be a valid ActivCode, that you can change the enumeration values and highly coupled to the GetHashCode implementation:

enum MarketDataExchange
{
    NONE,
    NBBO = 371857150,
    AMEX = 372029405,
    BSE = 372029408,
    BATS = -1850320644,
    NSE = 372029407,
    CHX = -284236702,
    NYSE = 372029412,
    ARCA = -734575383,
    NASDAQ = 372029421,
    NASDAQ_ADF = -1137859911,
    CBOE = 372029419,
    PHLX = 372029430,
    DIRECTEDGE = 372029429
}

public static MarketDataExchange GetMarketDataExchange(string ActivCode)
{
    if (ActivCode == null) return MarketDataExchange.NONE;

    return (MarketDataExchange)ActivCode.GetHashCode();
}

这篇关于你如何使这个 switch 语句尽可能快?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！