我们可以将此任务并行化吗？
给定一个C字符串（以NULL字符常量终止的字符数组），我们必须找到字符串的长度。 能否为N个执行线程建议一些并行化的方法。 我有问题分为子问题，因为访问不存在的arrays的位置将给出分段错误。
编辑 ：我并不担心并行执行此任务可能会带来更大的开销。 只是想知道是否可以这样做（使用类似openmp等的东西）
不，它不能。 因为每个步骤都需要知道先前的状态（我们是否在前一个char上遇到null）。 您一次只能安全地检查1个字符。
想象一下，你正在翻转岩石，你必须停在下面的白色油漆（null），否则你会死（也就是段故障等）。
你不能让人们“相互提前”，因为白色的油漆岩石可能介于两者之间。
拥有多个人（线程/进程）只是轮流成为转向下一个摇滚的人。 他们永远不会在彼此同时翻过岩石。
它可能甚至不值得尝试。 如果字符串很短，则开销将大于处理速度的增益。 如果字符串非常长，速度可能会受到内存速度的限制，而不受CPU处理速度的限制。
我只说一个标准的C字符串，这是无法做到的。 但是，如果您可以定义一个包含与进程一样多的字符的个人终止字符串 – 它就是直截了当的。
你知道那个char数组的最大大小吗？ 如果是这样，您可以在不同的junks中进行并行搜索，并返回具有最小索引的终结符的索引。 因此，您只能处理已分配的内存，您无法获得段错误。
当然，这并不像s_nairs那样复杂，但非常直接。 例：
#include #include #include #include int main(int argc, char **argv) { int N=1000; char *str = calloc(N, sizeof(char)); strcpy(str, "This is a test string!"); fprintf(stdout, "%s\n", str); int nthreads = omp_get_num_procs(); int i; int ind[nthreads]; for( i = 0; i < nthreads; i++){ ind[i] = -1; } int procn; int flag; #pragma omp parallel private(procn, flag) { flag = 1; procn = omp_get_thread_num(); #pragma omp for for( i = 0; i < N; i++){ if (str[i] == '\0' && flag == 1){ ind[procn] = i; flag = 0; } } } int len = 0; for( i = 0; i < nthreads; i++){ if(ind[i]>-1){ len = ind[i]; break; } } fprintf(stdout,"strlen %d\n", len); free(str); return 0; } 在Windows中包含SEH __try块中的不安全内存读取时，你可以做一些像这样丑陋的事情：
#include #include #include #include #define N 2 DWORD WINAPI FindZeroThread(LPVOID lpParameter) { const char* volatile* pp = (const char* volatile*)lpParameter; __try { while (**pp) { (*pp) += N; } } __except (EXCEPTION_EXECUTE_HANDLER) { *pp = NULL; } return 0; } size_t pstrlen(const char* s) { int i; HANDLE handles[N]; const char* volatile ptrs[N]; const char* p = (const char*)(UINT_PTR)-1; for (i = 0; i < N; i++) { ptrs[i] = s + i; handles[i] = CreateThread(NULL, 0, &FindZeroThread, (LPVOID)&ptrs[i], 0, NULL); } WaitForMultipleObjects(N, handles, TRUE /* bWaitAll */, INFINITE); for (i = 0; i < N; i++) { CloseHandle(handles[i]); if (ptrs[i] && p > ptrs[i]) p = ptrs[i]; } return (size_t)(p - s); } #define LEN (20 * 1000 * 1000) int main(void) { char* s = malloc(LEN); memset(s, '*', LEN); s[LEN - 1] = 0; printf("strlen()=%zu pstrlen()=%zu\n", strlen(s), pstrlen(s)); return 0; }
输出：
strlen()=19999999 pstrlen()=19999999
我认为使用MMX / SSE指令以某种并行的方式加速代码可能会更好。
编辑 ：毕竟，这在Windows上可能不是一个好主意，请参阅Raymond Chen的IsBadXxxPtr应该真正称为CrashProgramRandomly 。
让我承认这一点，
以下代码是使用C＃而不是C编写的。您可以将我想要表达的想法联系起来。 大多数内容来自并行模式（Microsoft是并行方法的草案文档）
为了尽可能地进行最佳静态分区，您需要能够提前准确地预测所有迭代需要多长时间。 这很少可行，导致需要更动态的分区，系统可以快速适应不断变化的工作负载。 我们可以通过转移到分区权衡频谱的另一端来解决这个问题，同时尽可能多地进行负载均衡。
要做到这一点，我们可以让线程竞争迭代，而不是将每个线程推送到给定的一组索引来处理。 我们使用剩余迭代池来处理，最初开始填充所有迭代。 在处理完所有迭代之前，每个线程都会进入迭代池，删除迭代值，处理它，然后重复。 通过这种方式，我们可以以贪婪的方式实现可能的最佳负载均衡水平的近似值（真正的最优化只能通过事先知道每次迭代需要多长时间才能实现）。 如果线程在处理特定的长迭代时遇到困难，则其他线程将在此期间通过池中的处理工作进行补偿。 当然，即使采用这种方案，您仍然可以发现自己远远没有达到最佳分区（如果一个线程碰巧遇到几个比其余部分大得多的工作，可能会发生这种情况），但不知道处理时间多少如果要完成一项工作，就可以做更多的工作。
这是一个将负载平衡发挥到极致的示例实现。 迭代值池保持为表示下一次可用迭代的单个整数，并通过primefaces递增此整数来处理“删除项目”中涉及的线程：
public static void MyParallelFor( int inclusiveLowerBound, int exclusiveUpperBound, Action body) { // Get the number of processors, initialize the number of remaining // threads, and set the starting point for the iteration. int numProcs = Environment.ProcessorCount; int remainingWorkItems = numProcs; int nextIteration = inclusiveLowerBound; using (ManualResetEvent mre = new ManualResetEvent(false)) { // Create each of the work items. for (int p = 0; p < numProcs; p++) { ThreadPool.QueueUserWorkItem(delegate { int index; while ((index = Interlocked.Increment( ref nextIteration) - 1) < exclusiveUpperBound) { body(index); } if (Interlocked.Decrement(ref remainingWorkItems) == 0) mre.Set(); }); } // Wait for all threads to complete. mre.WaitOne(); } }