Common Lisp：为什么 lparallel 在分配数组元素时有问题？
Common Lisp: Why does lparallel have problems with assigning array elements?
我编写了一个函数，可以将许多元素从一个数组复制到另一个数组。我想使用 lparallel 的 (pdotimes) 函数来加速它。代码如下所示：
(pdotimes (i (size output))
(setf (row-major-aref output i)
(row-major-aref input (dostuff i))))
(dostuff) 函数对行优先输出索引 i 进行算术运算，将其转换为行优先输入索引。当我 运行 这个函数时，结果往往是这样的：
#2A((9 9 9 9 9 9 9 9 9 9 5 5 5 5 5 5 5 5 5 5)
(9 9 9 9 9 9 9 9 9 9 5 5 5 5 5 5 5 5 5 5)
(9 9 9 9 9 9 9 9 9 9 5 5 5 5 5 5 5 5 5 5)
(9 9 9 9 9 9 9 9 9 9 5 5 5 5 5 5 5 5 5 5)
(9 0 9 9 9 9 9 9 9 9 5 5 0 5 5 5 5 5 5 5)
(9 9 9 9 9 9 9 9 9 9 5 5 5 5 5 5 5 5 5 5)
(9 9 9 9 9 9 9 9 9 9 5 5 5 5 5 5 5 5 5 5)
(9 9 9 9 9 9 9 9 9 9 5 5 5 5 5 5 5 5 5 5)
(9 9 9 9 9 9 0 0 9 9 5 5 5 5 5 5 5 5 5 5)
(9 9 9 9 9 9 9 9 9 9 5 5 5 5 5 5 5 5 5 5))
该函数应该连接左侧的 9 矩阵和右侧的 5 矩阵。但请注意，那里也有几个 0。零是输出矩阵的初始值，这意味着这些元素没有被分配。
元素的非赋值看似随机； 运行函数多次，零会出现在不同的地方。出于某种原因，这些元素被遗漏了。
我试过在未来包装这个函数，像这样：
(let ((f (future (pdotimes ...))))
(force f))
但这也不管用。我注意到的一件事是，线程数越多，数组越小，遗漏的元素就越多。这表明数组元素分配以某种方式相互破坏。
我也尝试过使用 (pmap-into) 将函数的结果映射到一个向量中，该向量被替换为输出，但以不同的方式失败了：而不是在未分配元素的地方显示 0，元素被分配到错误的地方。如果数组包含重复的“1 2 3 4”子向量，有时会出现“1 2 2”序列，例如
据我所知，线程应该可以同时分配同一个数组中的不同元素，但是 Common Lisp 有这方面的问题吗？我是否需要实施锁以确保分配同步发生？如果同时分配是一个问题，我希望看到更多未分配的元素。任何帮助表示赞赏。
编辑：我似乎找到了防止这种情况发生的方法，但没有找到根本原因。在 SBCL 中尝试运行宁这个：
(let ((output (make-array '(20 20) :initial-element 0 :element-type '(unsigned-byte 7))))
(check-type output simple-array)
(pdotimes (i (array-total-size output) output)
(setf (row-major-aref output i)
(random-elt '(1 2 3 4 5 6)))))
输出中不会出现零。现在在 SBCL 中试试这个：
(let ((output (make-array '(20 20) :initial-element 0 :element-type '(unsigned-byte 4))))
(check-type output simple-array)
(pdotimes (i (array-total-size output) output)
(setf (row-major-aref output i)
(random-elt '(1 2 3 4 5 6)))))
看到很多零。我刚刚用 CCL 测试了这个，输出很好。我打算尝试其他一些 CL，但到目前为止，这似乎是一个 SBCL 问题。出于某种原因，SBCL 在对元素小于 7 位的数组进行并发赋值时遇到问题。字符数组很好，浮点数和 t 型数组也是如此。
我写了一个最小的例子如下（使用 lparallel 和 alexandria）
(let ((output (make-array '(20 20) :initial-element '_)))
(check-type output simple-array)
(pdotimes (i (array-total-size output) output)
(setf (row-major-aref output i)
(random-elt '(a b c d e f g h)))))
它每次都按如下方式始终如一地填充输出网格：
#2A((B G C D H A F E D C F D F G D F A C G G)
(C E D D F A H A F D G E G A C C F G E G)
(H C A E C F E H E D F G D B H B B A H D)
(D H G H H A E B G D E G D E G C E A B B)
(B E H G E E C D A H F A E C F D D A H H)
(C B D D G D H H D G H C A A H G B G C C)
(H H D D C F D B H B H G B C F G H F D E)
(F B C C A H D H G H C D G G D F E G A B)
(A E G C C H F C F C E F H H D E C H H D)
(H G H C D F G E D E C E A H C E A H H H)
(E C B E E C A D B G A F C B G A D G F D)
(H D D H A E A A G D H B H D A G A G C F)
(C D F H D G A D E C F C C D F A F F C H)
(H H D E C B C B E B B G G H H B A A E H)
(G F C C B F C D D D H F A B C F F C A B)
(D A H B B F H B B B F F H B G B H C F E)
(A G H C D H A H C H B F D D A G A E B G)
(G H A D H G B E A A B F C E G G G D E D)
(C E G F H F A A A H D D F B F C H B G B)
(H E H D D F F H E G G A A E D G C H H B))
但是，3.6 遍历规则和副作用
表示如果您修改填充指针（对于非向量不可能）或调整数组（？），后果是未定义的。但是你的例子看起来不像数组正在调整。
抱歉这个问题，但它适用于 dotimes 吗？我的示例在您的机器上是否有效？
这是一个略带推测性的答案，但我有理由相信它是正确的。
如果实现支持其元素大小（以位为单位）小于机器可以读取和写入内存的最小对象的数组，并且如果它存储这些数组而没有浪费 space（即，实际上，拥有它们的唯一目的），那么更新数组元素的唯一方法是：
- 从内存中读取包含元素的最小对象；
- 用元素更新对象；
- 写回。
由于写入不同的数组元素会导致从内存中读取和写入 相同的 最小对象，这在没有互锁的情况下存在多线程是不安全的，通常会有灾难性的性能影响。
可能所有 CL 实现都有这样的数组，用于现代机器，不能以位数组的形式将单个位写入内存。 SBCL 也有 2 位和 4 位的元素类型数组，假设机器可以读取和写入没有小于 8 位的对象也在这个区域。如果需要多次读取和写入来加载和存储一个对象，具有非常大对象类型的数组也可能会遇到同样的问题。
应该可以查看使用此类数组的代码的反汇编来查看行为。也可能是这样的数组比具有较大元素类型的数组具有更低的性能（实验上这对于 x64 上的 SBCL 是正确的：初始化 (unsigned-byte 4) 数组的代码比初始化 [=12= 的代码慢 2.5 倍]数组）。
请注意，我强烈怀疑从数组攻击代码中获得良好性能的正确方法是以一种相当聪明的方式在核心之间划分数组。
也就是说，这是一种初始化半字节数组 ((unsigned-byte 4)s) 的方法，我认为它应该是安全的，前提是可以原子写入的最小对象是一个字节。诀窍是一次写入一对奇偶地址：
(defun initialize-nibble-array (a)
;; the idea is to put some pattern in it I can see if it has holes
(declare (type (array (unsigned-byte 4) *) a))
(let ((s (array-total-size a)))
(pdotimes (i (truncate s 2))
(let ((rmi (* i 2)))
(setf (row-major-aref a rmi) (mod rmi 8)
(row-major-aref a (1+ rmi)) (mod (1+ rmi) 8))))
(when (oddp s)
;; if the array has an odd number of elements we've missed one
;; at the end
(setf (row-major-aref a (- s 1)) (mod (- s 1) 8)))
a))
我编写了一个函数，可以将许多元素从一个数组复制到另一个数组。我想使用 lparallel 的 (pdotimes) 函数来加速它。代码如下所示：
(pdotimes (i (size output))
(setf (row-major-aref output i)
(row-major-aref input (dostuff i))))
(dostuff) 函数对行优先输出索引 i 进行算术运算，将其转换为行优先输入索引。当我 运行 这个函数时，结果往往是这样的：
#2A((9 9 9 9 9 9 9 9 9 9 5 5 5 5 5 5 5 5 5 5)
(9 9 9 9 9 9 9 9 9 9 5 5 5 5 5 5 5 5 5 5)
(9 9 9 9 9 9 9 9 9 9 5 5 5 5 5 5 5 5 5 5)
(9 9 9 9 9 9 9 9 9 9 5 5 5 5 5 5 5 5 5 5)
(9 0 9 9 9 9 9 9 9 9 5 5 0 5 5 5 5 5 5 5)
(9 9 9 9 9 9 9 9 9 9 5 5 5 5 5 5 5 5 5 5)
(9 9 9 9 9 9 9 9 9 9 5 5 5 5 5 5 5 5 5 5)
(9 9 9 9 9 9 9 9 9 9 5 5 5 5 5 5 5 5 5 5)
(9 9 9 9 9 9 0 0 9 9 5 5 5 5 5 5 5 5 5 5)
(9 9 9 9 9 9 9 9 9 9 5 5 5 5 5 5 5 5 5 5))
该函数应该连接左侧的 9 矩阵和右侧的 5 矩阵。但请注意，那里也有几个 0。零是输出矩阵的初始值，这意味着这些元素没有被分配。
元素的非赋值看似随机； 运行函数多次，零会出现在不同的地方。出于某种原因，这些元素被遗漏了。
我试过在未来包装这个函数，像这样：
(let ((f (future (pdotimes ...))))
(force f))
但这也不管用。我注意到的一件事是，线程数越多，数组越小，遗漏的元素就越多。这表明数组元素分配以某种方式相互破坏。
我也尝试过使用 (pmap-into) 将函数的结果映射到一个向量中，该向量被替换为输出，但以不同的方式失败了：而不是在未分配元素的地方显示 0，元素被分配到错误的地方。如果数组包含重复的“1 2 3 4”子向量，有时会出现“1 2 2”序列，例如
据我所知，线程应该可以同时分配同一个数组中的不同元素，但是 Common Lisp 有这方面的问题吗？我是否需要实施锁以确保分配同步发生？如果同时分配是一个问题，我希望看到更多未分配的元素。任何帮助表示赞赏。
编辑：我似乎找到了防止这种情况发生的方法，但没有找到根本原因。在 SBCL 中尝试运行宁这个：
(let ((output (make-array '(20 20) :initial-element 0 :element-type '(unsigned-byte 7))))
(check-type output simple-array)
(pdotimes (i (array-total-size output) output)
(setf (row-major-aref output i)
(random-elt '(1 2 3 4 5 6)))))
输出中不会出现零。现在在 SBCL 中试试这个：
(let ((output (make-array '(20 20) :initial-element 0 :element-type '(unsigned-byte 4))))
(check-type output simple-array)
(pdotimes (i (array-total-size output) output)
(setf (row-major-aref output i)
(random-elt '(1 2 3 4 5 6)))))
看到很多零。我刚刚用 CCL 测试了这个，输出很好。我打算尝试其他一些 CL，但到目前为止，这似乎是一个 SBCL 问题。出于某种原因，SBCL 在对元素小于 7 位的数组进行并发赋值时遇到问题。字符数组很好，浮点数和 t 型数组也是如此。
我写了一个最小的例子如下（使用 lparallel 和 alexandria）
(let ((output (make-array '(20 20) :initial-element '_)))
(check-type output simple-array)
(pdotimes (i (array-total-size output) output)
(setf (row-major-aref output i)
(random-elt '(a b c d e f g h)))))
它每次都按如下方式始终如一地填充输出网格：
#2A((B G C D H A F E D C F D F G D F A C G G)
(C E D D F A H A F D G E G A C C F G E G)
(H C A E C F E H E D F G D B H B B A H D)
(D H G H H A E B G D E G D E G C E A B B)
(B E H G E E C D A H F A E C F D D A H H)
(C B D D G D H H D G H C A A H G B G C C)
(H H D D C F D B H B H G B C F G H F D E)
(F B C C A H D H G H C D G G D F E G A B)
(A E G C C H F C F C E F H H D E C H H D)
(H G H C D F G E D E C E A H C E A H H H)
(E C B E E C A D B G A F C B G A D G F D)
(H D D H A E A A G D H B H D A G A G C F)
(C D F H D G A D E C F C C D F A F F C H)
(H H D E C B C B E B B G G H H B A A E H)
(G F C C B F C D D D H F A B C F F C A B)
(D A H B B F H B B B F F H B G B H C F E)
(A G H C D H A H C H B F D D A G A E B G)
(G H A D H G B E A A B F C E G G G D E D)
(C E G F H F A A A H D D F B F C H B G B)
(H E H D D F F H E G G A A E D G C H H B))
但是，3.6 遍历规则和副作用 表示如果您修改填充指针（对于非向量不可能）或调整数组（？），后果是未定义的。但是你的例子看起来不像数组正在调整。
抱歉这个问题，但它适用于 dotimes 吗？我的示例在您的机器上是否有效？
这是一个略带推测性的答案，但我有理由相信它是正确的。
如果实现支持其元素大小（以位为单位）小于机器可以读取和写入内存的最小对象的数组，并且如果它存储这些数组而没有浪费 space（即，实际上，拥有它们的唯一目的），那么更新数组元素的唯一方法是：
- 从内存中读取包含元素的最小对象；
- 用元素更新对象；
- 写回。
由于写入不同的数组元素会导致从内存中读取和写入 相同的 最小对象，这在没有互锁的情况下存在多线程是不安全的，通常会有灾难性的性能影响。
可能所有 CL 实现都有这样的数组，用于现代机器，不能以位数组的形式将单个位写入内存。 SBCL 也有 2 位和 4 位的元素类型数组，假设机器可以读取和写入没有小于 8 位的对象也在这个区域。如果需要多次读取和写入来加载和存储一个对象，具有非常大对象类型的数组也可能会遇到同样的问题。
应该可以查看使用此类数组的代码的反汇编来查看行为。也可能是这样的数组比具有较大元素类型的数组具有更低的性能（实验上这对于 x64 上的 SBCL 是正确的：初始化 (unsigned-byte 4) 数组的代码比初始化 [=12= 的代码慢 2.5 倍]数组）。
请注意，我强烈怀疑从数组攻击代码中获得良好性能的正确方法是以一种相当聪明的方式在核心之间划分数组。
也就是说，这是一种初始化半字节数组 ((unsigned-byte 4)s) 的方法，我认为它应该是安全的，前提是可以原子写入的最小对象是一个字节。诀窍是一次写入一对奇偶地址：
(defun initialize-nibble-array (a)
;; the idea is to put some pattern in it I can see if it has holes
(declare (type (array (unsigned-byte 4) *) a))
(let ((s (array-total-size a)))
(pdotimes (i (truncate s 2))
(let ((rmi (* i 2)))
(setf (row-major-aref a rmi) (mod rmi 8)
(row-major-aref a (1+ rmi)) (mod (1+ rmi) 8))))
(when (oddp s)
;; if the array has an odd number of elements we've missed one
;; at the end
(setf (row-major-aref a (- s 1)) (mod (- s 1) 8)))
a))