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.
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.
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
in ./configure on the Cygwin.
Last edit: Tatsuro MATSUOKA 2023-03-30
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.
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()
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>').
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.
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.
Last edit: Tatsuro MATSUOKA 2023-03-30
"Linux" in your list must be one that uses glibc. For example, Alpine Linux uses musl as standard C library.
Yes
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.
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.
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
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 .I have tried it on MacOS and it works fine.
I have tested using the current git master sources.
Results for points_overlaps were attached.
Last edit: Tatsuro MATSUOKA 2023-04-01
The attached one-line patch will probably make it sort the points also.
The patch fixes the case for points_overlaps.gp on both MinGW and Cygwin.
Thanks!
Thank you for your efforts in resolving this issue.