#2604 Failure of depth sort among overlapping surfaces (environment dependent)

[Hiroki Motoyoshi]

Depending on the compiled environment, the depth sort in splot may fail for overlapping surfaces. This is likely due to the fact that the qsort function used for depth sort behaves differently depending on the C language library. Especially, the behavior depends on whether the implementation of the qsort function is stable sort or unstable sort, which does or does not preserve the order of elements of the same value.

I discovered this phenomenon on MacOS environment. According to 'man', qsort function in the C library of the MacOS system is not stable,

The algorithms implemented by qsort(), qsort_r(), and heapsort() are not stable; that is,
if two members compare as equal, their order in the sorted array is undefined. The
mergesort() algorithm is stable.

As a test, I simply replaced the 'qsort' function with the 'mergesort' function which has the same API as 'qsort' and was able to draw without problems even on MacOS.

On the other hand, I had no problem on Rockey Linux. It is said that glibc uses a kind of merge sort as 'qsort', but I could not find an exact description.

I have not checked the situation in other environments (other BSDs, Windows ...)

I suppose that this has never been a problem because there is no need to draw multiple surfaces that fully or partially overlap in the normal case.

Here is a test script:

set term pngcairo

f(x,y) = 5*exp(-((x+y)**2+((x-y)/2)**2))

set xrange [-3:3]
set yrange [-3:3]
set samples 30
set isosamples 30
set xyplane 0
unset colorbox

set output "case_pm3d.png"
set pm3d border lt -1 lw .1
set pm3d depthorder
set style fill solid 0.3
splot f(x,y) with pm3d fc "red" notitle, \
      f(x,y) with pm3d fc "green" notitle

set output "case_hidden3d.png"
set hidden3d
splot f(x,y) with lines notitle, \
      f(x,y) with lines notitle

Attached are the results of the above test scripts for the qsort and mergesort cases respectively on MacOS.

[Ethan Merritt]

Thanks for the feedback and help with configuration conventions.
I have committed it for 6.1 as configuration option
./configure --with-mergesort

I tested under linux but not under an O/S that actually offers mergesort. So try it out and tell me if I got something wrong.

[Tatsuro MATSUOKA]

On the MinGW and the Cygwin, similar phenomena that are the same as the MacOS were observed as I reported. The MinGW and the Cygwin seem not to have merge sort. Defining WITH_MERGESORT gives link errors on the MinGW and --with-mergesort gives

Use mergesort rather than qsort:                 no (not found in library)

in ./configure on the Cygwin.

[Hiroki Motoyoshi]

My apologies. I may have misled you as if mergesort was in the standard C library.

As Hans-Bernhard pointed out, mergesort is a function that is only available on BSD-like operating systems (it is included in libc) and not otherwise.

Also, perhaps non-glibc systems cannot get the drawings that glibc's stable sort achieves, so this mergesort-reliant countermeasure will leave glibc or non-BSD systems behind.

[Ethan Merritt]

So we get back to the earlier question - what library is your mergesort coming from? It would be easy enough to add that library name via AC_SEARCHLIBS()

[Hiroki Motoyoshi]

I believe that mergesort is a unique implementation of BSD-based systems and is not found in other systems.

If you are on a BSD-like system, it is in libc ('#include <stdlib.h>').

[Ethan Merritt]

So if I am understanding everyone correctly, the current state is things is:
linux: qsort is stable
BSD: qsort is unstable, mergesort is provided by libc
macOS: qsort is unstable, mergesort is provided (by libc?) ?
mingw: qsort is unstable, no mergesort in libc
Cygwin: qsort is unstable, no mergesort in libc

If that is corrent, then my attempt at configure --with -mergesort resolves this issue for BSD and macOS. Is that correct?

My previous patchset adding a sequence field to pm3d quadrangles would be a partial solution for mingw and Cygwin, but involves adding extra code to gnuplot.

[Tatsuro MATSUOKA]

For the MinGW and the Cygwin, the above is right.
I executed the Google search.
The glibc used as the libc in the Linux.
In the glibc, the mergesort is used for the qsort if heap area is avaliable.
So, it is natural the qsort gives good results in the Linux.
On the MinGW, the msvcrt.dll is used as the libc.
On the Cygwin, the newlib is used as libc.
The msvcrt.dll is the WIndows standard libc so that the compliers provided by the Microsoft probably have the same behaviors as those in the MinGW.

[Hiroki Motoyoshi]

linux: qsort is stable

"Linux" in your list must be one that uses glibc. For example, Alpine Linux uses musl as standard C library.

macOS: qsort is unstable, mergesort is provided (by libc?) ?

Yes

BSD: qsort is unstable, mergesort is provided by libc

May be Yes. Sorry, I have not tested on any BSD-like OS other than MacOS.

The 'mergesort' as a function is unique to the BSD-like system. So, from the point of view of avoiding complications, we may give up --with-mergesort, which is available only for BSDs, and consolidate it into --with-stable-sort because of the lack of common stable sort.

[Hiroki Motoyoshi]

For example, Alpine Linux uses musl as standard C library.

I was able to run gnuplot on Alpine Linux with Docker and I attach the results of the first example.
Musl's implementation of qsort seems to be an unstable sort with an algorithm called smoothsort.

[Ethan Merritt]

commit c5530094134f8e47fe74953f207673c0ef08bcf3 (HEAD -> master, origin/master, origin/HEAD, stable-sort)
Author: Ethan A Merritt merritt@u.washington.edu
Date: Thu Mar 30 17:59:14 2023 -0700

2nd try at a configuration option to request a stable sort for pm3d

This change subsumes the check for mergesort into a wider set of
alternatives explored by
        ./configure --enable-stable-sort

The qsort implementation in glibc is stable; i.e. elements that test
as equal are guaranteed to retain their origin order.
The relevance to gnuplot is that if either "pm3d depthorder" or
"set hidden3d" is used to render two surfaces with identical [x,y,z],
the first will be consistently occluded by the second.

However the qsort provided by BSD and macOS is not stable.
Those systems may provide mergesort as a stable alternative.

Other non-glibc platforms including mingw and Cygwin do not provide a stable sort.
On these platforms, identical surfaces sorted for either pm3d or hidden3d
are rendered inconsistently.  Any given quadrangle or line segment may
be rendered with the properties of either of the requested surfaces.

Gnuplot will now try to pick an appropriate stable sort if possible
and otherwise add code so that pm3d depth-sorting is stable.
There is not yet a fallback for hidden3d processing if the platform
does not offer a stable sort.

./configure --with-stable-sort
     1) Use mergesort if the system provides it, otherwise qsort.
     2) If neither mergesort nor glibc's qsort is available
        add a sequence field to pm3d quadrangles to be used as a
        secondary sort key.

Bug #2604
See earlier commits b992a505 103cc301 9282ff70

[Ethan Merritt]

And a follow-on commit to do something similar for hidden3d processing of "splot with lines".

I said earlier that the only property available for a second sort key was the line style, which is true. But in testing I find it is probably acceptable to overload the p_number field of the line style to hold a plot sequence number. That field is normally used only by style linespoints and has been ignored in hidden3d processing .

[Hiroki Motoyoshi]

I have tried it on MacOS and it works fine.

[Tatsuro MATSUOKA]

I have tested using the current git master sources.

• masked_surface.gp (OK!)
• from_boxes3d.gp (OK!)
• pm3d_at_base.gp (OK!)
• case_hidden3d.gp (OK!)
• points_overlaps.gp (NG)

Results for points_overlaps were attached.

[Ethan Merritt]

The attached one-line patch will probably make it sort the points also.

[Tatsuro MATSUOKA]

The patch fixes the case for points_overlaps.gp on both MinGW and Cygwin.
Thanks!

[Hiroki Motoyoshi]

Thank you for your efforts in resolving this issue.