Why does the ordering of work items seem to make a big difference in performance for ElementWiseKernel?

[11Kclarke]

I've been using ElementWiseKernel for fractal zooms. I decided to shuffle the input, a flattened 2d array of complex numbers, in the hope that it would more evenly distribute values that need longer to resolve.
However, I've found that randomly shuffling the input has made the ElementWiseKernel take twice as long to run. The .get() command to retrieve the data goes from approximately 2.5 seconds to 5 seconds. With no changes, I can see other than the order of the input array.

If someone could explain what's happening here it would be much appreciated.
Here's a python function for recreating what I'm seeing. Its been pulled from a larger project but you should just need to run the above function with the compiled kernel for "mapcl"

def StabilityFractalPyOpenCL(x1,x2,y1,y2,SideLength,mapcl,queue,Divlim=2.0,maxdepth=30,cycles=False,cycleacc=None,shuffle=False):
    extent = [x1,x2,y1,y2]
    origTime=timeit.default_timer()
    Stabilities=createstartvals(x1,x2,y1,y2,SideLength)
    print(f"Time To create startvals: {timeit.default_timer()-origTime}")
    Stabilities=Stabilities.flatten()
    if shuffle:
        Time=timeit.default_timer()
        orderTemplate = np.arange(SideLength**2)
        shuf_order = orderTemplate
        np.random.shuffle(shuf_order)
        Stabilities=Stabilities[shuf_order]
        shuffletime = timeit.default_timer()-Time
        print(shuffletime)
    Stabilities=cl.array.to_device(queue,Stabilities)
    Xlength=int(np.ceil(abs((x1-x2)/(y1-y2)*SideLength)))
    Ylength=int(np.ceil((SideLength**2)/Xlength))

    Time=timeit.default_timer()
    mapcl(Stabilities,maxdepth,np.float64(Divlim))
    Stabilities=np.real(Stabilities.get())
    print(f"Time OpenCl: {timeit.default_timer()-Time}")
    if shuffle:
        Time=timeit.default_timer()
        unshuf_order = np.zeros_like(orderTemplate)
        unshuf_order[shuf_order] = np.arange(SideLength**2)  
        Stabilities=Stabilities[unshuf_order]
        unshuffletime = timeit.default_timer()-Time
        print(unshuffletime)
        print("total shuffle unshuffle time:")
        print(shuffletime+unshuffletime)
    print(f"whole generatorfucntion time {timeit.default_timer()-origTime}")
    return Stabilities.reshape(Xlength,Ylength),extent

paired with this preamble and ElementWiseKernel, though I imagine it isn't specific

`

preamble="""
#define PYOPENCL_DEFINE_CDOUBLE
#include <pyopencl-complex.h>
"""
`

StabilityFractalNoCycle=

`

int Counter = 0;
dtype_t Const=X[i];//dont rename
bool notfound = true;
while (dtype_abs(X[i])<DivLim && Counter<N)
{
    Counter+=1;
    X[i]=      cdouble_add(Const, cdouble_powr(X[i], 2 )  );
}

`

[inducer]

Memory access patterns matter.

[11Kclarke]

Hi,
Thanks for the reply. I've tried to research memory access patterns, and I'm still very confused as why my code is running so much faster when the input array is ordered.
I don't think any work item is communicating with any other work item. The logic for randomly shuffling was a pixel adjacent to a pixel that took a long time to generate is more likely to be an expensive pixel. I was hoping to more evenly distribute the work between work groups.
Could you please explain or point to resources explaining how I could better implement this optimization?
Im also very confused and curious why the ordering of the array has such an effect on speed through memory access. It almost seems like the array is being presorted before any computation is applied. Any more details you could shine on that would be greatly appreciated.

[11Kclarke]

Hey,
It makes sense to me now. Going to leave my explanation to encase it helps someone else. There's only 1 instruction reader per workgroup, so within a kernel, it's disadvantageous for branching unless each item in the workgroup will follow the same branch. While the input was ordered it meant items in the same workgroup were likely to follow the same branch. This saves much more time than splitting the more expensive branches across work groups.