c++ - 线程安全，在C++中有序映射/哈希？

coder 2024-02-22 原文

在C++中实现线程安全有序(note1)映射/哈希的最佳方法是什么？又是一种快速查找的数据结构(又称队列)，不同线程可以在不同线程之间进行迭代，偶尔插入或删除元素，而不会干扰其他线程的 Activity ？

std::map不是线程安全的，它的操作也不是原子的-尽管只有擦除会使迭代器

无效

将整个函数包装在整个map类中并不能解决问题-您可以在那里使用松散的迭代器来指向一个节点，该节点将被另一个线程擦除。它应该锁定并防止删除，直到当前线程是唯一引用它的线程为止，或者使用UNIX文件系统样式的“悬挂但删除后仍然有效的引用”方法

tbb::concurrent_hash_map设计为线程安全的，但其迭代器在删除其 key 后仍然无效。即使Value是一个智能指针，也不会保留数据，因为迭代器中的引用会丢失。

可以通过遍历键而不是迭代器来使用tbb:concurrent_hash_map(可以像std::map那样将键查找为O(1)而不是O(log N))，但是由于它是哈希值，因此缺少顺序-重要的是，如果某个键被另一个线程中的擦除操作悬空，则没有明显的方法告诉代码跳回到哈希中与该键最近的元素。

std::unordered_map有可能会尝试陪审团寻找最接近的元素，如果您的 key 是通过存储桶访问功能删除的。但是std::unordered_map不被认为是线程安全的(尽管它可能被包装为线程安全的)。 tbb::concurrent_hash_map是线程安全的(受上述约束的约束)，但是它不允许足够的存储桶访问权限来执行此操作。

如果某个键被另一个线程删除，则可以通过键而不是迭代器访问的

std::map可以在映射中找到下一个最近的元素。但是，每个查找将是O(log N)而不是O(1)。

同样，如前所述，std::map是非原子的。它必须被包装。使用键代替迭代器还需要包装整个类，因为必须将通常采用或返回迭代器的所有函数更改为采用键或返回键。

我读过的一个站点上的某人说std::map不管在线程环境中(与哈希相比)都不能很好地工作，因为线程在树的重新平衡方面不能很好地发挥作用，尽管我真的不知道为什么会这样甚至是否普遍适用/准确。

您认为最好的是什么？

**注1:当我写“ordered”时，我的意思是仅从“具有一个可以迭代的可靠顺序”的角度来看，而不是“迭代必须按键的顺序进行”。在写完这些之后，我意识到我的一些用例实际上关心的是迭代的顺序(大多数不是)。但是无论哪种方式，我都可以通过将链接列表处理为Value类型来评审适当的排序。只是缓慢的丑陋和潜在的问题/疏忽...

**注2:新思想。糟糕的 map 没有根据其迭代器类型进行模板化...要更改构建在std::map上的迭代器有多难？我以前一直在考虑让迭代器进行引用计数(例如std::shared_ptr)，但是我一直错误地考虑在迭代器自身内部使用辅助数据结构来实现引用计数，并且结果总是太丑陋/慢/不切实际。但是，现在让我想到的是，可以将引用计数包含在 map 的key:value对的Value中。也就是说，每个值都将包括A)一个引用计数器(默认值= 0)，每个插入器在到达它时都会递增(操作符=，operator++，operator--等)，并在离开它时递减。 B)擦除功能设置的擦除标志(默认= false)。每当迭代器将引用计数器减为零时，如果设置了擦除标志，则它将实际擦除它。

在我看来，虽然这对性能造成了影响(额外的增量/减量/检查)，但是每次您要逐步遍历结构时，都不必进行完整的 map 查找，这当然没什么大不了的。谁能想到实现此目标的实用方法？

最佳答案

由于某些原因，您错过了 tbb::concurrent_unordered_map ，它是具有线程安全迭代支持的哈希表。它基于拆分顺序列表算法，其中除哈希表外，元素还以容器范围的列表结构连接，因此迭代很简单。但是由于它不支持并发擦除，因此不能完全满足您的要求。

这是一个基本问题，在没有内存回收机制的情况下，很难在一个并发数据结构中同时融合快速遍历和安全擦除属性，您必须在此处选择:安全性/一致性或速度。

在某些限制和警告下，您可以按照this blog中的说明同时进行遍历和删除。基本上说，只要您可以交错(相互排除)遍历和擦除，就可以将tbb::concurrent_hash_map与find＆insert一起用于并发遍历。该博客建议使用复查模式进行其他优化。但是可以简化为以下内容:

for(iterator = table.begin(); iterator != table.end(); iterator++ ) {
    accessor acc;
    // a key cannot be changed thus it is safe to read it without lock
    table.find( acc, iterator->first );   // now get the get the lock
    if( acc->second.market_for_deletion )
        table.erase( acc );               // erase only by accessor
}

从本质上讲，您的注释2适用于current_hash_map情况，因为最大的开销不是来自查找(对于相邻元素，不太可能发生高速缓存未命中)，而是来自与两个锁(内部存储桶的锁和元素的访问器)的同步。

但是，如果这种遍历方法的速度太慢或太笨拙(依赖于实现细节)，但是您仍然迫切需要能够删除并发哈希表的元素，请考虑使用RW锁，例如tbb::spin_rw_mutex和tbb::concurrent_unordered_map。您需要找到一个最佳位置，在该位置可以不太频繁地获取读锁，以实现迭代，查找和插入而不会产生太多开销，并且也不太经常执行写锁下的擦除操作。可能需要其他方案才能标记和收集足够的元素，然后才能真正删除它们。例如。这是此类哈希表类的伪代码:

class concurrent_hash_table_with_erase_and_traverse {
    tbb::concurrent_unordered_map my_map;
    tbb::spin_rw_mutex            my_lock; // acquired as writer for cleanup only
    tbb::atomic<size_t>           my_trash_count; // indicates # of items for erase

public:
    void init_thread_for_concurrent_ops() { my_lock.lock_read(); }
    void release_thread()                 { my_lock.unlock(); } // assuming reader lock
    mapped_type read(key_type k) {
        // assert: under read lock (thread is initialized)
        if(my_trash_count > threshold) {  // time to remove items
            my_lock.unlock(); // release reader
            // waiting all the threads to enter this container
            // TODO: re-implement with try_lock and checking the condition 
            my_lock.lock();   // acquire writer

            if(my_trash_count > threshold) { // double-check
                my_trash_count = 0;
                for( auto it = my_map.begin(); it != my_map.end(); ) {
                    auto _it = it++;
                    if( _it->is_marked_for_erase )
                        my_map.unsafe_erase( _it );
                }
            }
            my_lock.unlock();    // release writer
            my_lock.lock_read(); // acquire reader
        }
        return my_map[k]; // note: access is not protected like in concurrent_hash_map
    }
    void safe_erase(key_type k) {
        // assert: under read lock
        my_map[k].is_marked_for_erase = true;
        my_trash_count++;
    }
};

关于c++ - 线程安全，在C++中有序映射/哈希？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33356115/

amp 43 map concurrent 的 c++multithreading c++11 stdmap tbb

有关c++ - 线程安全，在C++中有序映射/哈希？的更多相关文章

ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2
我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server
ruby - 如何使用 Ruby aws/s3 Gem 生成安全 URL 以从 s3 下载文件 - 2
我正在编写一个小脚本来定位aws存储桶中的特定文件，并创建一个临时验证的url以发送给同事。(理想情况下，这将创建类似于在控制台上右键单击存储桶中的文件并复制链接地址的结果)。我研究过回形针，它似乎不符合这个标准，但我可能只是不知道它的全部功能。我尝试了以下方法:defauthenticated_url(file_name,bucket)AWS::S3::S3Object.url_for(file_name,bucket,:secure=>true,:expires=>20*60)end产生这种类型的结果:...-1.amazonaws.com/file_path/file.zip.A
ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2
我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat
ruby - RuntimeError(自动加载常量 Apps 多线程时检测到循环依赖 - 2
我收到这个错误:RuntimeError(自动加载常量Apps时检测到循环依赖当我使用多线程时。下面是我的代码。为什么会这样？我尝试多线程的原因是因为我正在编写一个HTML抓取应用程序。对Nokogiri::HTML(open())的调用是一个同步阻塞调用，需要1秒才能返回，我有100,000多个页面要访问，所以我试图运行多个线程来解决这个问题。有更好的方法吗？classToolsController0)app.website=array.join(',')putsapp.websiteelseapp.website="NONE"endapp.saveapps=Apps.order("
ruby - 如何在 Grape 中定义哈希数组？ - 2
我使用Ember作为我的前端和GrapeAPI来为我的API提供服务。前端发送类似:{"service"=>{"name"=>"Name","duration"=>"30","user"=>nil,"organization"=>"org","category"=>nil,"description"=>"description","disabled"=>true,"color"=>nil,"availabilities"=>[{"day"=>"Saturday","enabled"=>false,"timeSlots"=>[{"startAt"=>"09:00AM","endAt"=>
ruby - 如何安全地删除文件？ - 2
在Ruby中是否有Gem或安全删除文件的方法？我想避免系统上可能不存在的外部程序。“安全删除”指的是覆盖文件内容。最佳答案如果您使用的是*nix，一个很好的方法是使用exec/open3/open4调用shred:`shred-fxuz#{filename}`http://www.gnu.org/s/coreutils/manual/html_node/shred-invocation.html检查这个类似的帖子:Writingafileshredderinpythonorruby?
ruby - 在哈希的键数组中追加元素 - 2
查看我的Ruby代码:h=Hash.new([])h[0]=:word1h[1]=h[1]输出是:Hash={0=>:word1,1=>[:word2,:word3],2=>[:word2,:word3]}我希望有Hash={0=>:word1,1=>[:word2],2=>[:word3]}为什么要附加第二个哈希元素(数组)？如何将新数组元素附加到第三个哈希元素？最佳答案如果您提供单个值作为Hash.new的参数(例如Hash.new([])，完全相同的对象将用作每个缺失键的默认值。这就是您所拥有的，那是你不想要的。您可以改用
ruby - 使用 `+=` 和 `send` 方法 - 2
如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:
ruby - 如何让Ruby捕获线程中的语法错误 - 2
我正在尝试使用ruby编写一个双线程客户端，一个线程从套接字读取数据并将其打印出来，另一个线程读取本地数据并将其发送到远程服务器。我发现的问题是Ruby似乎无法捕获线程内的错误，这是一个示例:#!/usr/bin/rubyThread.new{loop{$stdout.puts"hi"abc.putsefsleep1}}loop{sleep1}显然，如果我在线程外键入abc.putsef，代码将永远不会运行，因为Ruby将报告“undefinedvariableabc”。但是，如果它在一个线程内，则没有错误报告。我的问题是，如何让Ruby捕获这样的错误？或者至少，报告线程中的错误？
ruby - 在 Ruby 中创建按公共(public)键值分组的新哈希 - 2
假设我有一个在Ruby中看起来像这样的哈希:{:ie0=>"Hi",:ex0=>"Hey",:eg0=>"Howdy",:ie1=>"Hello",:ex1=>"Greetings",:eg1=>"Goodday"}有什么好的方法可以将它变成如下内容:{"0"=>{"ie"=>"Hi","ex"=>"Hey","eg"=>"Howdy"},"1"=>{"ie"=>"Hello","ex"=>"Greetings","eg"=>"Goodday"}} 最佳答案您要求一个好的方法来做到这一点，所以答案是:一种您或同事可以在六个月后理解

c++ - 线程安全，在C++中有序映射/哈希？

有关c++ - 线程安全，在C++中有序映射/哈希？的更多相关文章

随机推荐