小编sci*_*ete的帖子

我有两个线程,一个在紧密循环中工作,另一个偶尔需要与第一个执行同步:

// thread 1
while(1)
{
    lock(work);
    // perform work
    unlock(work);
}

// thread 2
while(1)
{
    // unrelated work that takes a while
    lock(work);
    // synchronizing step
    unlock(work);
}

我的意图是,通过获取锁,线程2可以有效地暂停线程1并执行必要的同步.线程1还可以通过解锁来提供暂停,如果线程2没有等待锁定,则重新锁定并返回工作.

我遇到的问题是互斥是不公平的,所以线程1快速重新锁定互斥锁并使线程2饿死.我试图使用pthread_yield,到目前为止似乎运行正常,但我不确定它是否会起作用所有系统/核心数量.有没有办法保证线程1总能屈服于线程2,即使在多核系统上也是如此？

处理此同步过程的最有效方法是什么？

我在循环中有一些关键的分支代码,运行大约2 ^ 26次.分支预测不是最优的,因为m是随机的.如何删除分支,可能使用按位运算符？

bool m;
unsigned int a;
const unsigned int k = ...; // k >= 7
if(a == 0)
    a = (m ? (a+1) : (k));
else if(a == k)
    a = (m ?     0 : (a-1));
else
    a = (m ? (a+1) : (a-1));

以下是由gcc -O3以下内容生成的相关程序集:

.cfi_startproc
movl    4(%esp), %edx
movb    8(%esp), %cl
movl    (%edx), %eax
testl   %eax, %eax
jne L15
cmpb    $1, %cl
sbbl    %eax, %eax
andl    $638, %eax
incl    %eax
movl …

我需要实现一个字符串搜索算法,该算法在位文本中找到位模式(匹配可能不是字节/字对齐).对于初学者,我实现了Boyer-Moore算法,但比较单个位对于我的目的来说太慢了.所以我尝试实现一个基于阻塞的版本,可以比较本文所述的整个字节/单词,但它已变得复杂且无法管理(部分原因是由于我不完全理解我在做什么.)

有没有人有这样的算法很好的实现？

我的具体用例是模式长度N >= 32,文本窗口2N和打包成ints的位.同样N在这种情况下是字符大小的倍数N % 8 == 0.我预处理一次并多次使用更改文本,比如Boyer-Moore.第一场比赛就是我所需要的.表现是关键.

编辑:在成功实现Blocked Boyer-Moore算法后,我注意到没有任何改进(我的一点一点版本更快!)这可能是我自己的错误,因为我一直在绞尽脑汁并优化它到目前为止没有多行评论就没有意义,但它仍然较慢.在这里.