[Emacs-diffs] trunk r117765: Add vectors support to Fsort.

[Emacs-diffs] trunk r117765: Add vectors support to Fsort.

[Eli Zaretskii]

Thanks for doing this.

This change should have a corresponding NEWS entry.

Re: [Emacs-diffs] trunk r117765: Add vectors support to Fsort.

[Jordon Biondo]

fns-tests.el is failing on trunk for me. I get the Re-entering top level after C stack overflow error, then: Fatal error 11: Segmentation faultAbort trap: 6, if I try to do anything else. It looks like qsort_r needs special treatment on darwin and bsd systems.

For now I’m just undefining HAVE_QSORT_R.

Thanks,
Jordon

On Aug 29, 2014, at 6:46 AM, Eli Zaretskii <eliz@gnu.org> wrote:

> Thanks for doing this.
> 
> This change should have a corresponding NEWS entry.
> 

Re: [Emacs-diffs] trunk r117765: Add vectors support to Fsort.

[Dmitry Antipov]

On 08/29/2014 06:21 PM, Jordon Biondo wrote:

> fns-tests.el is failing on trunk for me. I get the Re-entering top level
> after C stack overflow error, then: Fatal error 11: Segmentation fault
> Abort trap: 6, if I try to do anything else. It looks like qsort_r needs
> special treatment on darwin and bsd systems.

Oops. I have a VM with FreeBSD 10.0 and will take a look.

BTW, what is your output from the following program:

#include <stdio.h>
#include <sys/resource.h>

int
main (int argc, char *argv[])
{
   struct rlimit rlim;
   getrlimit (RLIMIT_STACK, &rlim);
   printf ("%ld %ld\n", rlim.rlim_cur, rlim.rlim_max);
   return 0;
}

Running as root, I get:

536870912 536870912

512 Mb stack?  I just don't believe in that.

Dmitry

Re: [Emacs-diffs] trunk r117765: Add vectors support to Fsort.

[Jordon Biondo]

On Aug 29, 2014, at 11:41 AM, Dmitry Antipov <dmantipov@yandex.ru> wrote:

> Oops. I have a VM with FreeBSD 10.0 and will take a look.
> 
> BTW, what is your output from the following program:

Thanks,

8720000 67104768 is my output.

Also, I sent a report and hacky patch to bug-gnu-emacs about it with further information.

Thanks,
Jordon

Re: [Emacs-diffs] trunk r117765: Add vectors support to Fsort.

[Dmitry Antipov]

On 08/29/2014 07:50 PM, Jordon Biondo wrote:

> 8720000 67104768 is my output.

Good, 8720000 looks like a valid limit.

Can you also verify that running an endless recursion
with huge max-lisp-eval-depth, e.g.:

(setq max-specpdl-size 83200000
       max-lisp-eval-depth 640000)

(defun f1 () (f1))

(f1)

doesn't crash but throws you to a top-level editing loop?

Thanks,
Dmitry

Re: [Emacs-diffs] trunk r117765: Add vectors support to Fsort.

[Jordon Biondo]

[-- Attachment #1: Type: text/plain, Size: 492 bytes --]


On Aug 29, 2014, at 12:34 PM, Dmitry Antipov <dmantipov@yandex.ru> wrote:

> doesn't crash but throws you to a top-level editing loop?

With this I get the same Error, Re-entering top level after C stack overflow and I can keep editing for a time.

I will seg fault soon after, however. I haven’t nailed down exactly what causes the seg fault after, but doing tab-completion in the mini buffer will seg fault if I run your code and get the overflow error first.

Thanks,
Jordon


[-- Attachment #2: Type: text/html, Size: 1275 bytes --]

Re: [Emacs-diffs] trunk r117765: Add vectors support to Fsort.

[Stefan Monnier]

>> doesn't crash but throws you to a top-level editing loop?
> With this I get the same Error, Re-entering top level after C stack overflow
> and I can keep editing for a time.
> I will seg fault soon after, however. I haven’t nailed down exactly what
> causes the seg fault after, but doing tab-completion in the mini buffer will
> seg fault if I run your code and get the overflow error first.

Maybe the GC doesn't scan the altstack?


        Stefan

Change Emacs 'sort' API to use three-way comparison

[Paul Eggert]

One infelicity I noticed in the recent change to 'sort' in the trunk is 
that the new implementation calls its predicate twice for each 
comparison.  This is because the Lisp API says the comparison function 
returns a boolean (nil or non-nil), whereas qsort_r wants the comparison 
function to return a ternary value (-1, 0, or 1). If the predicate is 
expensive, the new Fsort can be twice as slow as the old.  We could tune 
it but I don't see how to get it any faster than 1.5x slower than 
before, assuming random input and an expensive comparison function.

To fix this I propose changing the API for 'sort' so that its function 
argument is no longer a predicate, but instead returns a negative 
integer, 0, or a positive integer.  For compatibility with old code, it 
would treat nil as if it were nonpositive (thus requiring a reverse 
comparison) and noninteger nonnil values as if they were positive.  This 
wouldn't be 100% upward-compatible, because if an existing predicate 
returns a nonpositive integer to stand for 'true' there will be a silent 
change to behavior, but I expect such usage is so rare that we don't 
need to worry about it.

Re: Change Emacs 'sort' API to use three-way comparison

[David Kastrup]

Paul Eggert <eggert@cs.ucla.edu> writes:

> One infelicity I noticed in the recent change to 'sort' in the trunk
> is that the new implementation calls its predicate twice for each
> comparison.  This is because the Lisp API says the comparison function
> returns a boolean (nil or non-nil), whereas qsort_r wants the
> comparison function to return a ternary value (-1, 0, or 1). If the
> predicate is expensive, the new Fsort can be twice as slow as the old.
> We could tune it but I don't see how to get it any faster than 1.5x
> slower than before, assuming random input and an expensive comparison
> function.

Can someone give an executive summary why we would be using a "qsort_r"
here?

"sort" sorts a list.  There is really not much of a point in not using a
mergesort here, resulting in a stable sort and requiring only a binary
comparison function.

Quicksorts make sense when sorting arrays.

-- 
David Kastrup

Re: [Emacs-diffs] trunk r117765: Add vectors support to Fsort.

[Dmitry Antipov]

On 08/29/2014 10:31 PM, Stefan Monnier wrote:
> Maybe the GC doesn't scan the altstack?

This is not needed because the altstack is used only for SIGSEGV
handler (handle_sigsegv), which doesn't operate on GC'ed objects.

Dmitry

Re: Change Emacs 'sort' API to use three-way comparison

[Lars Ingebrigtsen]

Paul Eggert <eggert@cs.ucla.edu> writes:

> One infelicity I noticed in the recent change to 'sort' in the trunk
> is that the new implementation calls its predicate twice for each
> comparison.  This is because the Lisp API says the comparison function
> returns a boolean (nil or non-nil), whereas qsort_r wants the
> comparison function to return a ternary value (-1, 0, or 1). If the
> predicate is expensive, the new Fsort can be twice as slow as the old.
> We could tune it but I don't see how to get it any faster than 1.5x
> slower than before, assuming random input and an expensive comparison
> function.

Uhm.  Why has somebody introduced a new sort that's slower than the old
sort?

As somebody who sorts a lot of things in Emacs, that sounds kinda
... bad.

-- 
(domestic pets only, the antidote for overdose, milk.)
  bloggy blog http://lars.ingebrigtsen.no/

Re: Change Emacs 'sort' API to use three-way comparison

[Paul Eggert]

Lars Ingebrigtsen wrote:
> Why has somebody introduced a new sort that's slower than the old
> sort?

In what sense is the new code slower?  If you sort a list, the code is 
the same as before.

Re: Change Emacs 'sort' API to use three-way comparison

[Lars Ingebrigtsen]

Paul Eggert <eggert@cs.ucla.edu> writes:

> In what sense is the new code slower?  If you sort a list, the code is
> the same as before.

I don't know anything about this code other than what you wrote about
it:

> We could tune it but I don't see how to get it any faster than 1.5x
> slower than before, assuming random input and an expensive comparison
> function.

It's slower in the sense that you said it's slower.

-- 
(domestic pets only, the antidote for overdose, milk.)
  bloggy blog http://lars.ingebrigtsen.no/

Re: Change Emacs 'sort' API to use three-way comparison

[Paul Eggert]

Lars Ingebrigtsen wrote:
> It's slower in the sense that you said it's slower.

Ah yes, sorry, I should have been clearer in my earlier remarks.  The 
new vector-sorting code can be considerably slower than sorting a list 
of the same length, if the comparison predicate is expensive.  But 
existing code (which just sorts lists) should not be affected by this, 
as the list-sorting code is the same as before.

Anyway, I'm looking into a fix for all this.

Re: [Emacs-diffs] trunk r117765: Add vectors support to Fsort.

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

    This is not needed because the altstack is used only for SIGSEGV
    handler (handle_sigsegv), which doesn't operate on GC'ed objects.

This discussion suggests that that point ought to be mentioned
in comments in more places.

-- 
Dr Richard Stallman
President, Free Software Foundation
51 Franklin St
Boston MA 02110
USA
www.fsf.org  www.gnu.org
Skype: No way! That's nonfree (freedom-denying) software.
  Use Ekiga or an ordinary phone call.