Mergesort algorithm occasionally generates garbage values in sorted vector

[sergiodguezc]

Hello there,

I hope this message finds you well. I am reaching out because I believe I may have encountered a bug in the algorithm mergesort of the containers-accelerate project.

While using this project to build a bioinspired library for optimizing continuous functions, I have noticed that occasionally after sorting a vector, the vector becomes filled with some garbage. Specifically, when creating a new point, I constrain it to the search space. However, at the end of the execution, there are some points that are outside the bounds.

I am not entirely certain if this issue is related to the sortBy function and the initialization of the output vector with undefined values. However, it is a possibility that I wanted to bring to your attention.

I apologize if I have overlooked something or if this issue has already been reported. As someone who is new to this subject, I appreciate your patience and understanding. Thank you for your time and consideration.

Best regards, Sergio Domínguez

[tmcdonell]

Hi Sergio,

Thanks for your message, and your interest in Accelerate! That sounds like a cool project you are working on (:

There might indeed be a problem with the merge-sort function. If you can give me further details on your setup (which backend, OS, etc.) and a small reproducible test case, I can try to look into it.

In the mean time, you could try using the quicksort method instead, and see if that works around the problem for you (that one is a bit better tested so I am slightly more confident that it is correct).

[sergiodguezc]

Hi Trevor,

Thanks for getting back to me! I'm glad to hear that you're interested in my project :).

Regarding the merge-sort function, I appreciate your willingness to help. My setup is running on GHC 8.10.7, using LLVM.Native as the backend, and I'm running it on Linux 6.1.22-1-lts. Unfortunately, I don't have a reproducible test case at the moment, but I'll work on creating one and will send it to you as soon as I can.

I tried the quicksort method that you suggested, and it works well for my purposes. However, I was using merge sort because at each iteration the previous vector is already ordered, and the algorithm just needs to insert the new values while maintaining the sorted order. This makes it more efficient than quicksort in some cases.

In any case, I appreciate your help and suggestions, and I'll keep working on finding a solution to this problem.

Thanks again for your help!

[sergiodguezc]

Here it is the reproducible test case:

import Data.Array.Accelerate as A
import qualified Data.Array.Accelerate.LLVM.Native as CPU
import Data.Array.Accelerate.Data.Sort.Merge

testMerge :: IO ()
testMerge = do
  let xs = use $ A.fromList (Z :. 1000) [0, 1 ..] :: Acc (Vector Int)
      ys = use $ A.fromList (Z :. 1000) [2, 4 ..] :: Acc (Vector Int)

      T2 loop _ =
        A.awhile
          (\(T2 _ i) -> A.map (A.< 1000) i)
          ( \(T2 xs' i) ->
              let i' = the i :: Exp Int
                  i'' = i' + 1
                  ys' = A.take i' ys :: Acc (Vector Int)
                  sorted = A.take 1000 $ sort (xs' A.++ ys') :: Acc (Vector Int)
               in T2 sorted (unit i'')
          )
          (T2 xs (unit 0))

  print $ CPU.run $ A.take 20 loop
  print $ CPU.run $ A.take 20 xs
  print $ CPU.run $ A.take 20 ys

Results: Vector (Z :. 20) [-8888828770332863923,-8888828770332863923,-8888828770332863923,-7072078906498459620,-7072078906498459620,-707207890649845 9620,-7072078906498459620,-6948079798528238165,-6948079798528238165,-6948079798528238165,-6332140206658740844,-6332140206658740844,-6332140 206658740844,-6332140206658740844,-6332140206658740844,-6332140206658740844,-6332140206658740844,-6332140206658740844,-6332140206658740844, -6332140206658740844] Vector (Z :. 20) [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19] Vector (Z :. 20) [2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40]

[sergiodguezc]

Hello again and sorry for the spam.

I think have identified a potential error in the newIndex function. In situations where the last block is on the left and the searchMinIndex is greater than searchMaxIndex, the binarySearch function returns a negative number of blocks, leading to overlapping indexes with the previous block pair.

Now, I'm no expert, but I think a quick fix would be to add something like this

    countOtherBlock' = binarySearch values cmp value (not left) searchMinIndex searchMaxIndex
    countOtherBlock  = countOtherBlock' < 0 && searchMaxIndex == valueCount ? (0, countOtherBlock')

I am not sure if this patch could lead to other potential bugs. Thanks for taking the time to read my message. Let me know what you think.