From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Dmitry Antipov Newsgroups: gmane.emacs.devel Subject: Benchmarking temporary Lisp objects [Was: Re: [RFC] temporary Lisp_Strings] Date: Wed, 03 Sep 2014 14:23:29 +0400 Message-ID: <5406EC21.4060200@yandex.ru> References: <5405BE5D.1090003@yandex.ru> <5405DE8B.4050201@yandex.ru> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="------------090603040306000407050002" X-Trace: ger.gmane.org 1409739838 17791 80.91.229.3 (3 Sep 2014 10:23:58 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 3 Sep 2014 10:23:58 +0000 (UTC) To: Emacs development discussions Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Wed Sep 03 12:23:51 2014 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1XP7jD-0000fY-6C for ged-emacs-devel@m.gmane.org; Wed, 03 Sep 2014 12:23:51 +0200 Original-Received: from localhost ([::1]:43864 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XP7jC-0003fK-Nw for ged-emacs-devel@m.gmane.org; Wed, 03 Sep 2014 06:23:50 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:37483) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XP7j3-0003dy-Fy for emacs-devel@gnu.org; Wed, 03 Sep 2014 06:23:48 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XP7iw-000231-Dz for emacs-devel@gnu.org; Wed, 03 Sep 2014 06:23:41 -0400 Original-Received: from forward1l.mail.yandex.net ([84.201.143.144]:40850) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XP7iw-00022b-1d for emacs-devel@gnu.org; Wed, 03 Sep 2014 06:23:34 -0400 Original-Received: from smtp13.mail.yandex.net (smtp13.mail.yandex.net [95.108.130.68]) by forward1l.mail.yandex.net (Yandex) with ESMTP id A216D1520D29 for ; Wed, 3 Sep 2014 14:23:30 +0400 (MSK) Original-Received: from smtp13.mail.yandex.net (localhost [127.0.0.1]) by smtp13.mail.yandex.net (Yandex) with ESMTP id 3B3FBE402FC for ; Wed, 3 Sep 2014 14:23:30 +0400 (MSK) Original-Received: from unknown (unknown [37.139.80.10]) by smtp13.mail.yandex.net (nwsmtp/Yandex) with ESMTPSA id DnYQVsysQj-NTOefBfM; Wed, 3 Sep 2014 14:23:29 +0400 (using TLSv1.2 with cipher AES128-SHA (128/128 bits)) (Client certificate not present) X-Yandex-Uniq: 9afa0573-66f8-4c9f-8742-79ab391a77ba DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail; t=1409739809; bh=xOD5WRKbif+R3lb0Y6SViF/tCHDlIHovlpAbXEdKHG4=; h=Message-ID:Date:From:User-Agent:MIME-Version:To:Subject: References:In-Reply-To:Content-Type; b=vPhTUfZcYTRrtyacyDEun5Sp8u793fKFFTAPXi47sPtEIdLt1i9DywgEVlzmEe5yE 4rFXBaO+blXDRwoJN+w3hT1Y5Su6365fr3JR3eZWTrFifocGMjMLePLqRMQcv1BdgU 28sLf57G+f0xAHyIG2wiGrNAoc9anxV53mE7HQ5Y= Authentication-Results: smtp13.mail.yandex.net; dkim=pass header.i=@yandex.ru User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.0 In-Reply-To: X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x [generic] [fuzzy] X-Received-From: 84.201.143.144 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:173976 Archived-At: This is a multi-part message in MIME format. --------------090603040306000407050002 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit To whom it may concern, I decided to start from conses and vectors just because this is simpler than strings. My experimental stuff is attached, and typical benchmark output may be something like: Average of 100: stack allocation is 6.879408 times faster for conses Average of 1000: stack allocation is 7.390145 times faster for conses Average of 10000: stack allocation is 4.154356 times faster for conses Average of 100000: stack allocation is 2.417694 times faster for conses Average of 10: stack allocation is 11.535833 times faster for vectors Average of 100: stack allocation is 4.731400 times faster for vectors Average of 1000: stack allocation is 1.443268 times faster for vectors Note that this is sustained allocation speed; since we're unlikely to allocate large amounts of Lisp data on stack, real speedup may vary. Questions: 1) Should alloca_vector fallback to Fmake_vector for large vectors? 2) Is there a way to rewrite alloca_xxx macros to avoid statement expressions? IIUC this is not portable beyond gcc and compilers that mimics it (clang, Intel's icc). Dmitry --------------090603040306000407050002 Content-Type: text/x-patch; name="cons_vector_benchmark.patch" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="cons_vector_benchmark.patch" =3D=3D=3D modified file 'src/alloc.c' --- src/alloc.c 2014-08-29 07:29:47 +0000 +++ src/alloc.c 2014-09-03 09:41:26 +0000 @@ -7118,8 +7118,76 @@ file, line, msg); terminate_due_to_signal (SIGABRT, INT_MAX); } -#endif -=0C + +/* Stress alloca with inconveniently-sized requests and check + whether all allocated areas may be used for Lisp_Object. */ + +static void +verify_alloca (void) +{ + int i; + enum { ALLOCA_CHECK_MAX =3D 256 }; + for (i =3D 0; i < ALLOCA_CHECK_MAX; i++) + { + char *ptr =3D alloca (i + 1); + eassert (valid_pointer_for_lisp_object (ptr)); + } +} + +#else /* not ENABLE_CHECKING */ + +#define verify_alloca() ((void) 0) + +#endif /* ENABLE_CHECKING */ + +DEFUN ("cons-benchmark", Fcons_benchmark, Scons_benchmark, 1, 1, 0, + doc: /* Benchmark cons allocation. */) + (Lisp_Object obj) +{ + double x, y; + ptrdiff_t i, max; + struct timespec ts; + + CHECK_NUMBER (obj); + max =3D XINT (obj); + + ts =3D current_timespec (); + for (i =3D 0, obj =3D Qnil; i < max; i++) + obj =3D Fcons (Qt, obj); + x =3D timespectod (timespec_sub (current_timespec (), ts)); + + ts =3D current_timespec (); + for (i =3D 0, obj =3D Qnil; i < max; i++) + obj =3D alloca_cons (Qt, obj); + y =3D timespectod (timespec_sub (current_timespec (), ts)); + + return Fcons (make_float (x), make_float (y)); +} + +DEFUN ("vector-benchmark", Fvector_benchmark, Svector_benchmark, 1, 1, 0= , + doc: /* Benchmark vector allocation. */) + (Lisp_Object obj) +{ + double x, y; + ptrdiff_t i, max; + struct timespec ts; + + CHECK_NUMBER (obj); + max =3D XINT (obj); + + ts =3D current_timespec (); + for (i =3D 0, obj =3D Qnil; i < max; i++) + obj =3D Fmake_vector (make_number (i + 1), Qnil); + x =3D timespectod (timespec_sub (current_timespec (), ts)); + + ts =3D current_timespec (); + for (i =3D 0, obj =3D Qnil; i < max; i++) + obj =3D alloca_vector (i + 1, Qnil); + y =3D timespectod (timespec_sub (current_timespec (), ts)); + + return Fcons (make_float (x), make_float (y)); +} + /* Initialization. */ =20 void @@ -7129,6 +7197,8 @@ purebeg =3D PUREBEG; pure_size =3D PURESIZE; =20 + verify_alloca (); + #if GC_MARK_STACK || defined GC_MALLOC_CHECK mem_init (); Vdead =3D make_pure_string ("DEAD", 4, 4, 0); @@ -7284,6 +7354,9 @@ #if GC_MARK_STACK =3D=3D GC_USE_GCPROS_CHECK_ZOMBIES defsubr (&Sgc_status); #endif + + defsubr (&Scons_benchmark); + defsubr (&Svector_benchmark); } =20 /* When compiled with GCC, GDB might say "No enum type named =3D=3D=3D modified file 'src/lisp.h' --- src/lisp.h 2014-09-02 18:05:00 +0000 +++ src/lisp.h 2014-09-03 09:37:46 +0000 @@ -4533,6 +4533,37 @@ memory_full (SIZE_MAX); \ } while (false) =20 +/* True if Lisp_Object may be placed at P. Used only + under ENABLE_CHECKING and optimized away otherwise. */ + +INLINE bool +valid_pointer_for_lisp_object (void *p) +{ + uintptr_t v =3D (uintptr_t) p; + return !(USE_LSB_TAG ? (v & ~VALMASK) : v >> VALBITS); +} + +/* Allocate Lisp_Cons on stack. */ + +#define alloca_cons(head, tail) \ + ({ struct Lisp_Cons *_c =3D alloca (sizeof *_c); \ + eassert (valid_pointer_for_lisp_object (_c)); \ + _c->car =3D (head), _c->u.cdr =3D (tail); \ + make_lisp_ptr (_c, Lisp_Cons); }) + +/* Allocate Lisp_Vector on stack, with respect to MAX_ALLOCA limit. */ + +#define alloca_vector(slots, init) \ + ({ struct Lisp_Vector *_v; \ + ptrdiff_t _i, _n =3D header_size + (slots) * word_size; \ + eassert (_n <=3D MAX_ALLOCA); \ + _v =3D alloca (_n); \ + eassert (valid_pointer_for_lisp_object (_v)); \ + _v->header.size =3D (slots); \ + for (_i =3D 0; _i < _v->header.size; _i++) \ + _v->contents[_i] =3D init; \ + make_lisp_ptr (_v, Lisp_Vectorlike); }) + /* Loop over all tails of a list, checking for cycles. FIXME: Make tortoise and n internal declarations. FIXME: Unroll the loop body so we don't need `n'. */ --------------090603040306000407050002 Content-Type: text/x-emacs-lisp; name="cons-vector-benchmark.el" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="cons-vector-benchmark.el" (defun cons-benchmark-test () (interactive) (dolist (size '(100 1000 10000 100000)) (let ((avg 0.0)) (dotimes (i 1000) (let ((data (cons-benchmark size))) (setq avg (+ avg (/ (car data) (cdr data)))))) (message "Average of %d: stack allocation is %f times faster for conses" size (/ avg 1000.0))))) (defun vector-benchmark-test () (interactive) (dolist (size '(10 100 1000)) (let ((avg 0.0)) (dotimes (i 1000) (let ((data (vector-benchmark size))) (setq avg (+ avg (/ (car data) (cdr data)))))) (message "Average of %d: stack allocation is %f times faster for vectors" size (/ avg 1000.0))))) --------------090603040306000407050002--