| 14 | // The bucket sort has 3 methods: sequential, atomic, and non-atomic. |
| 15 | |
| 16 | bool GB_transpose_method // if true: use GB_builder, false: use bucket |
| 17 | ( |
| 18 | const GrB_Matrix A, // matrix to transpose |
| 19 | int *nworkspaces_bucket, // # of slices of A for the bucket method |
| 20 | int *nthreads_bucket, // # of threads to use for the bucket method |
| 21 | GB_Context Context |
| 22 | ) |
| 23 | { |
| 24 | |
| 25 | //-------------------------------------------------------------------------- |
| 26 | // get inputs |
| 27 | //-------------------------------------------------------------------------- |
| 28 | |
| 29 | // if available, A->nvec_nonempty is used to select the method |
| 30 | int64_t anvec = (A->nvec_nonempty < 0) ? A->nvec : A->nvec_nonempty ; |
| 31 | int64_t anz = GB_nnz (A) ; |
| 32 | int64_t avlen = A->vlen ; |
| 33 | // int64_t avdim = A->vdim ; |
| 34 | int anzlog = (anz == 0) ? 1 : (int) GB_CEIL_LOG2 (anz) ; |
| 35 | int mlog = (avlen == 0) ? 1 : (int) GB_CEIL_LOG2 (avlen) ; |
| 36 | double bucket_factor ; |
| 37 | |
| 38 | // determine # of threads for bucket method |
| 39 | GB_GET_NTHREADS_MAX (nthreads_max, chunk, Context) ; |
| 40 | int nthreads = GB_nthreads (anz + avlen, chunk, nthreads_max) ; |
| 41 | |
| 42 | //-------------------------------------------------------------------------- |
| 43 | // select between the atomic and non-atomic bucket method |
| 44 | //-------------------------------------------------------------------------- |
| 45 | |
| 46 | bool atomics ; |
| 47 | if (nthreads <= 2) |
| 48 | { |
| 49 | // sequential bucket method: no atomics needed |
| 50 | // 2 threads: always use non-atomic method |
| 51 | atomics = false ; |
| 52 | } |
| 53 | else if ((double) nthreads * (double) avlen > (double) anz) |
| 54 | { |
| 55 | // non-atomic workspace is too high; use atomic method |
| 56 | atomics = true ; |
| 57 | } |
| 58 | else |
| 59 | { |
| 60 | // select between atomic and non-atomic methods. This rule is based on |
| 61 | // performance on a 4-core system with 4 threads with gcc 7.5. The icc |
| 62 | // compiler has much slower atomics than gcc and so atol should likely |
| 63 | // be smaller when using icc. |
| 64 | |
| 65 | int atol ; |
| 66 | if (anzlog < 14) |
| 67 | { |
| 68 | atol = -4 ; // fewer than 16K entries in A |
| 69 | } |
| 70 | else |
| 71 | { |
| 72 | switch (anzlog) |
| 73 | { |
no test coverage detected