无空“映射":回调解决方案是否比 tryGet() 慢? [英] Null-free "maps": Is a callback solution slower than tryGet()?
问题描述
在对的评论中>如何在无空设计中实现 List、Set 和 Map?"、Steven Sudit 和我开始讨论使用回调，带有找到"和未找到"情况的处理程序，与 tryGet() 方法，采用 out 参数和返回一个布尔值，指示是否已填充 out 参数.史蒂文坚持认为回调方法更复杂，几乎肯定会更慢；我坚持认为复杂性并没有更大，而且性能最坏相同.
In comments to "How to implement List, Set, and Map in null free design?", Steven Sudit and I got into a discussion about using a callback, with handlers for "found" and "not found" situations, vs. a tryGet() method, taking an out parameter and returning a boolean indicating whether the out parameter had been populated. Steven maintained that the callback approach was more complex and almost certain to be slower; I maintained that the complexity was no greater and the performance at worst the same.
但代码胜于雄辩，所以我想我会同时实现两者，看看我得到了什么.最初的问题在语言方面是相当理论化的(为了论证，假设这种语言甚至没有 null")——我在这里使用了 Java，因为这就是我所拥有的得心应手.Java 没有 out 参数，但它也没有一流的函数，所以从风格上来说，这两种方法应该同样糟糕.
But code speaks louder than words, so I thought I'd implement both and see what I got. The original question was fairly theoretical with regard to language ("And for argument sake, let's say this language don't even have null") -- I've used Java here because that's what I've got handy. Java doesn't have out parameters, but it doesn't have first-class functions either, so style-wise, it should suck equally for both approaches.
(题外话:就复杂性而言:我喜欢回调设计，因为它本质上强制 API 的用户处理这两种情况，而 tryGet() 设计要求调用者执行他们自己的样板条件检查，他们可能会忘记或出错.但是现在实现了两者，我可以理解为什么 tryGet() 设计看起来更简单，至少在短期内.)
(Digression: As far as complexity goes: I like the callback design because it inherently forces the user of the API to handle both cases, whereas the tryGet() design requires callers to perform their own boilerplate conditional check, which they could forget or get wrong. But having now implemented both, I can see why the tryGet() design looks simpler, at least in the short term.)
一、回调例子:
class CallbackMap<K, V> {
private final Map<K, V> backingMap;
public CallbackMap(Map<K, V> backingMap) {
this.backingMap = backingMap;
}
void lookup(K key, Callback<K, V> handler) {
V val = backingMap.get(key);
if (val == null) {
handler.handleMissing(key);
} else {
handler.handleFound(key, val);
}
}
}
interface Callback<K, V> {
void handleFound(K key, V value);
void handleMissing(K key);
}
class CallbackExample {
private final Map<String, String> map;
private final List<String> found;
private final List<String> missing;
private Callback<String, String> handler;
public CallbackExample(Map<String, String> map) {
this.map = map;
found = new ArrayList<String>(map.size());
missing = new ArrayList<String>(map.size());
handler = new Callback<String, String>() {
public void handleFound(String key, String value) {
found.add(key + ": " + value);
}
public void handleMissing(String key) {
missing.add(key);
}
};
}
void test() {
CallbackMap<String, String> cbMap = new CallbackMap<String, String>(map);
for (int i = 0, count = map.size(); i < count; i++) {
String key = "key" + i;
cbMap.lookup(key, handler);
}
System.out.println(found.size() + " found");
System.out.println(missing.size() + " missing");
}
}
现在，tryGet() 示例——尽我所能理解该模式(我很可能是错的):
Now, the tryGet() example -- as best I understand the pattern (and I might well be wrong):
class TryGetMap<K, V> {
private final Map<K, V> backingMap;
public TryGetMap(Map<K, V> backingMap) {
this.backingMap = backingMap;
}
boolean tryGet(K key, OutParameter<V> valueParam) {
V val = backingMap.get(key);
if (val == null) {
return false;
}
valueParam.value = val;
return true;
}
}
class OutParameter<V> {
V value;
}
class TryGetExample {
private final Map<String, String> map;
private final List<String> found;
private final List<String> missing;
private final OutParameter<String> out = new OutParameter<String>();
public TryGetExample(Map<String, String> map) {
this.map = map;
found = new ArrayList<String>(map.size());
missing = new ArrayList<String>(map.size());
}
void test() {
TryGetMap<String, String> tgMap = new TryGetMap<String, String>(map);
for (int i = 0, count = map.size(); i < count; i++) {
String key = "key" + i;
if (tgMap.tryGet(key, out)) {
found.add(key + ": " + out.value);
} else {
missing.add(key);
}
}
System.out.println(found.size() + " found");
System.out.println(missing.size() + " missing");
}
}
最后是性能测试代码:
public static void main(String[] args) {
int size = 200000;
Map<String, String> map = new HashMap<String, String>();
for (int i = 0; i < size; i++) {
String val = (i % 5 == 0) ? null : "value" + i;
map.put("key" + i, val);
}
long totalCallback = 0;
long totalTryGet = 0;
int iterations = 20;
for (int i = 0; i < iterations; i++) {
{
TryGetExample tryGet = new TryGetExample(map);
long tryGetStart = System.currentTimeMillis();
tryGet.test();
totalTryGet += (System.currentTimeMillis() - tryGetStart);
}
System.gc();
{
CallbackExample callback = new CallbackExample(map);
long callbackStart = System.currentTimeMillis();
callback.test();
totalCallback += (System.currentTimeMillis() - callbackStart);
}
System.gc();
}
System.out.println("Avg. callback: " + (totalCallback / iterations));
System.out.println("Avg. tryGet(): " + (totalTryGet / iterations));
}
在我第一次尝试时，回调的性能比 tryGet() 差 50%，这真的让我感到惊讶.但是，凭直觉，我添加了一些垃圾收集，并且性能损失消失了.
On my first attempt, I got 50% worse performance for callback than for tryGet(), which really surprised me. But, on a hunch, I added some garbage collection, and the performance penalty vanished.
这符合我的直觉，即我们基本上是在谈论采用相同数量的方法调用、条件检查等并重新安排它们.但后来，我写了代码，所以我很可能写了一个次优或次要惩罚的 tryGet() 实现.想法?
This fits with my instinct, which is that we're basically talking about taking the same number of method calls, conditional checks, etc. and rearranging them. But then, I wrote the code, so I might well have written a suboptimal or subconsicously penalized tryGet() implementation. Thoughts?
更新:根据来自 Michael Aaron Safyan 的评论，修复了TryGetExample 重用 OutParameter.
Updated: Per comment from Michael Aaron Safyan, fixed TryGetExample to reuse OutParameter.
推荐答案
David，感谢您抽出宝贵时间撰写本文.我是一名 C# 程序员，所以这些天我的 Java 技能有点模糊.因此，我决定移植您的代码并自己测试.我发现了一些有趣的差异和相似之处，就我而言，这些差异和相似之处非常值得入场.主要区别包括:
David, thanks for taking the time to write this up. I'm a C# programmer, so my Java skills are a bit vague these days. Because of this, I decided to port your code over and test it myself. I found some interesting differences and similarities, which are pretty much worth the price of admission as far as I'm concerned. Among the major differences are:
- 我不必实施 TryGet，因为它内置于 Dictionary 中.
- 为了使用本机 TryGet，我没有插入空值来模拟未命中，而是简单地省略了这些值.这仍然意味着
v = map[k]会将v设置为null，所以我认为这是一个正确的移植.事后看来，我可以插入空值并将(_map.TryGetValue(key, out value))更改为(_map.TryGetValue(key, out value) && value !=null))，但我很高兴我没有. - 我想要非常公平.因此，为了使代码尽可能紧凑和可维护，我使用了 lambda 演算符号，这让我可以轻松定义回调.这隐藏了设置匿名委托的大部分复杂性，并允许我无缝地使用闭包.具有讽刺意味的是，
Lookup的实现在内部使用了 TryGet. - 我没有声明一个新的 Dictionary 类型，而是使用扩展方法将
Lookup移植到标准字典上，大大简化了代码.
- I didn't have to implement TryGet because it's built into Dictionary.
- In order to use the native TryGet, instead of inserting nulls to simulate misses, I simply omitted those values. This still means that
v = map[k]would have setvtonull, so I think it's a proper porting. In hindsight, I could have inserted the nulls and changed(_map.TryGetValue(key, out value))to(_map.TryGetValue(key, out value) && value != null)), but I'm glad I didn't. - I want to be exceedingly fair. So, to keep the code as compact and maintainable as possible, I used lambda calculus notation, which let me define the callbacks painlessly. This hides much of the complexity of setting up anonymous delegates, and allows me to use closures seamlessly. Ironically, the implementation of
Lookupuses TryGet internally. - Instead of declaring a new type of Dictionary, I used an extension method to graft
Lookuponto the standard dictionary, much simplifying the code.
对于代码质量低于专业水平深表歉意，这里是:
With apologies for the less-than-professional quality of the code, here it is:
using System;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApplication1
{
static class CallbackDictionary
{
public static void Lookup<K, V>(this Dictionary<K, V> map, K key, Action<K, V> found, Action<K> missed)
{
V v;
if (map.TryGetValue(key, out v))
found(key, v);
else
missed(key);
}
}
class TryGetExample
{
private Dictionary<string, string> _map;
private List<string> _found;
private List<string> _missing;
public TryGetExample(Dictionary<string, string> map)
{
_map = map;
_found = new List<string>(_map.Count);
_missing = new List<string>(_map.Count);
}
public void TestTryGet()
{
for (int i = 0; i < _map.Count; i++)
{
string key = "key" + i;
string value;
if (_map.TryGetValue(key, out value))
_found.Add(key + ": " + value);
else
_missing.Add(key);
}
Console.WriteLine(_found.Count() + " found");
Console.WriteLine(_missing.Count() + " missing");
}
public void TestCallback()
{
for (int i = 0; i < _map.Count; i++)
_map.Lookup("key" + i, (k, v) => _found.Add(k + ": " + v), k => _missing.Add(k));
Console.WriteLine(_found.Count() + " found");
Console.WriteLine(_missing.Count() + " missing");
}
}
class Program
{
static void Main(string[] args)
{
int size = 2000000;
var map = new Dictionary<string, string>(size);
for (int i = 0; i < size; i++)
if (i % 5 != 0)
map.Add("key" + i, "value" + i);
long totalCallback = 0;
long totalTryGet = 0;
int iterations = 20;
TryGetExample tryGet;
for (int i = 0; i < iterations; i++)
{
tryGet = new TryGetExample(map);
long tryGetStart = DateTime.UtcNow.Ticks;
tryGet.TestTryGet();
totalTryGet += (DateTime.UtcNow.Ticks - tryGetStart);
GC.Collect();
tryGet = new TryGetExample(map);
long callbackStart = DateTime.UtcNow.Ticks;
tryGet.TestCallback();
totalCallback += (DateTime.UtcNow.Ticks - callbackStart);
GC.Collect();
}
Console.WriteLine("Avg. callback: " + (totalCallback / iterations));
Console.WriteLine("Avg. tryGet(): " + (totalTryGet / iterations));
}
}
}
我的性能期望，正如我在启发这个的文章中所说的那样，是没有一个比另一个更快或更慢.毕竟，大部分工作都在搜索和添加中，而不是在构建它的简单逻辑中.事实上，它在运行中略有不同，但我无法检测到任何一致的优势.
My performance expectations, as I said in the article that inspired this one, would be that neither one is much faster or slower than the other. After all, most of the work is in the searching and adding, not in the simple logic that structures it. In fact, it varied a bit among runs, but I was unable to detect any consistent advantage.
部分问题是我使用了一个低精度的计时器，而且测试时间很短，所以我将计数增加了 10 倍到 2000000，这有所帮助.现在回调慢了大约 3%，我认为这并不重要.在我相当慢的机器上，回调花费了 17773437，而 tryget 花费了 17234375.
Part of the problem is that I used a low-precision timer and the test was short, so I increased the count by 10x to 2000000 and that helped. Now callbacks are about 3% slower, which I do not consider significant. On my fairly slow machine, callbacks took 17773437 while tryget took 17234375.
现在，至于代码复杂度，有点不公平，因为 TryGet 是原生的，所以让我们忽略我不得不添加回调接口的事实.在调用点，lambda 符号在隐藏复杂性方面做得很好.如果有的话，它实际上比 TryGet 版本中使用的 if/then/else 更短，尽管我想我可以使用三元运算符使其同样紧凑.
Now, as for code complexity, it's a bit unfair because TryGet is native, so let's just ignore the fact that I had to add a callback interface. At the calling spot, lambda notation did a great job of hiding the complexity. If anything, it's actually shorter than the if/then/else used in the TryGet version, although I suppose I could have used a ternary operator to make it equally compact.
总的来说，我发现 C# 更优雅，其中只有一部分是由于我作为 C# 程序员的偏见.主要是，我不必定义和实现接口，这减少了管道开销.我还使用了非常标准的 .NET 约定，这似乎比 Java 中喜欢的那种风格更精简.
On the whole, I found the C# to be more elegant, and only some of that is due to my bias as a C# programmer. Mainly, I didn't have to define and implement interfaces, which cut down on the plumbing overhead. I also used pretty standard .NET conventions, which seem to be a bit more streamlined than the sort of style favored in Java.
这篇关于无空“映射":回调解决方案是否比 tryGet() 慢?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
