From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.bugs Subject: bug#25743: rehash-size ignored Date: Wed, 15 Feb 2017 14:18:54 -0500 Message-ID: NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: blaine.gmane.org 1487186421 14967 195.159.176.226 (15 Feb 2017 19:20:21 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Wed, 15 Feb 2017 19:20:21 +0000 (UTC) To: 25743@debbugs.gnu.org Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Wed Feb 15 20:20:16 2017 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ce57d-0003Kk-6E for geb-bug-gnu-emacs@m.gmane.org; Wed, 15 Feb 2017 20:20:13 +0100 Original-Received: from localhost ([::1]:42626 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ce57i-00078Z-Lp for geb-bug-gnu-emacs@m.gmane.org; Wed, 15 Feb 2017 14:20:18 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:60128) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ce57V-00075C-Pg for bug-gnu-emacs@gnu.org; Wed, 15 Feb 2017 14:20:07 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ce57S-00033t-Cu for bug-gnu-emacs@gnu.org; Wed, 15 Feb 2017 14:20:05 -0500 Original-Received: from debbugs.gnu.org ([208.118.235.43]:43147) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1ce57S-00033n-8y for bug-gnu-emacs@gnu.org; Wed, 15 Feb 2017 14:20:02 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1ce57S-00068W-4F for bug-gnu-emacs@gnu.org; Wed, 15 Feb 2017 14:20:02 -0500 X-Loop: help-debbugs@gnu.org Resent-From: Stefan Monnier Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Wed, 15 Feb 2017 19:20:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 25743 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: X-Debbugs-Original-To: bug-gnu-emacs@gnu.org Original-Received: via spool by submit@debbugs.gnu.org id=B.148718635323524 (code B ref -1); Wed, 15 Feb 2017 19:20:02 +0000 Original-Received: (at submit) by debbugs.gnu.org; 15 Feb 2017 19:19:13 +0000 Original-Received: from localhost ([127.0.0.1]:41346 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ce56e-00067L-TP for submit@debbugs.gnu.org; Wed, 15 Feb 2017 14:19:13 -0500 Original-Received: from eggs.gnu.org ([208.118.235.92]:40756) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ce56c-000679-TA for submit@debbugs.gnu.org; Wed, 15 Feb 2017 14:19:11 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ce56V-0002js-VS for submit@debbugs.gnu.org; Wed, 15 Feb 2017 14:19:05 -0500 Original-Received: from lists.gnu.org ([2001:4830:134:3::11]:41073) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1ce56V-0002jo-SZ for submit@debbugs.gnu.org; Wed, 15 Feb 2017 14:19:03 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:59960) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ce56T-0006yf-UR for bug-gnu-emacs@gnu.org; Wed, 15 Feb 2017 14:19:03 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ce56Q-0002j2-Oi for bug-gnu-emacs@gnu.org; Wed, 15 Feb 2017 14:19:01 -0500 Original-Received: from pruche.dit.umontreal.ca ([132.204.246.22]:36980) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ce56Q-0002ik-I5 for bug-gnu-emacs@gnu.org; Wed, 15 Feb 2017 14:18:58 -0500 Original-Received: from pastel.home (lechon.iro.umontreal.ca [132.204.27.242]) by pruche.dit.umontreal.ca (8.14.7/8.14.1) with ESMTP id v1FJIs6H005192 for ; Wed, 15 Feb 2017 14:18:54 -0500 Original-Received: by pastel.home (Postfix, from userid 20848) id 475F660594; Wed, 15 Feb 2017 14:18:54 -0500 (EST) X-NAI-Spam-Flag: NO X-NAI-Spam-Level: X-NAI-Spam-Threshold: 5 X-NAI-Spam-Score: 0.3 X-NAI-Spam-Rules: 5 Rules triggered BEC_TRC1=0.1, BEC_TRC1_W_GEN_SPAM_FEATRE=0.1, GEN_SPAM_FEATRE=0.1, EDT_SA_DN_PASS=0, RV5949=0 X-NAI-Spam-Version: 2.3.0.9418 : core <5949> : inlines <5699> : streams <1733073> : uri <2377740> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 208.118.235.43 X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.org gmane.emacs.bugs:129393 Archived-At: Package: Emacs Version: 26.0.50 Looking accidentally at maybe_resize_hash_table, I noticed that we don't obey resize_hash, although we do all the work needed for that. Worse, we make dangerous assumptions about the behavior of larger_vector: maybe_resize_hash_table takes `old_size' from `ASIZE (h->next)' and then uses rehash_size to compute the desired new_size. The problem comes here: set_hash_key_and_value (h, larger_vector (h->key_and_value, 2 * (new_size - old_size), -1)); set_hash_next (h, larger_vector (h->next, new_size - old_size, -1)); This says, that h->next and h->key_and_value are replaced by new vectors that are larger than the previous one so that they are large enough to accomodate new_size. The problem is that larger_vector's promise is to return a vector at least as large as requested, but sometimes larger. In practice the new vector is twice the size of the old vector. This means that rehash_size is ignored when it means to something smaller than twice the size. It *also* means that h->next may end up larger than planned. But `ASIZE (h->next)' is the definition of the hash-table's size, so if it's larger than planned, then it's indispensible to make sure that all other related tables are equally larger: h->key_and_value must always be at least twice the size of h->next. But the call above only makes sure the new h->key_and_value is at least twice the desired new_size but not twice the size of the new h->next. I think the right fix is to change the calls to larger_vector so that instead of requesting vectors "at least as large as new_size", we should request vectors "of size exactly new_size". That will fix both problems at the same time. The patch below implements it. Any objection? Stefan diff --git a/src/fns.c b/src/fns.c index 760a017dedf..62c834fac60 100644 --- a/src/fns.c +++ b/src/fns.c @@ -3536,19 +3535,19 @@ get_key_arg (Lisp_Object key, ptrdiff_t nargs, Lisp_Object *args, char *used) Lisp_Object larger_vector (Lisp_Object vec, ptrdiff_t incr_min, ptrdiff_t nitems_max) { + eassert (VECTORP (vec)); struct Lisp_Vector *v; - ptrdiff_t incr, incr_max, old_size, new_size; + ptrdiff_t old_size = ASIZE (vec); ptrdiff_t C_language_max = min (PTRDIFF_MAX, SIZE_MAX) / sizeof *v->contents; - ptrdiff_t n_max = (0 <= nitems_max && nitems_max < C_language_max + ptrdiff_t n_max = (nitems_max == 0 ? old_size + incr_min + : 0 < nitems_max && nitems_max < C_language_max ? nitems_max : C_language_max); - eassert (VECTORP (vec)); eassert (0 < incr_min && -1 <= nitems_max); - old_size = ASIZE (vec); - incr_max = n_max - old_size; - incr = max (incr_min, min (old_size >> 1, incr_max)); + ptrdiff_t incr_max = n_max - old_size; + ptrdiff_t incr = max (incr_min, min (old_size >> 1, incr_max)); if (incr_max < incr) memory_full (SIZE_MAX); - new_size = old_size + incr; + ptrdiff_t new_size = old_size + incr; v = allocate_vector (new_size); memcpy (v->contents, XVECTOR (vec)->contents, old_size * sizeof *v->contents); memclear (v->contents + old_size, incr * word_size); @@ -3828,10 +3827,10 @@ maybe_resize_hash_table (struct Lisp_Hash_Table *h) message ("Growing hash table to: %"pI"d", new_size); #endif - set_hash_key_and_value (h, larger_vector (h->key_and_value, - 2 * (new_size - old_size), -1)); - set_hash_next (h, larger_vector (h->next, new_size - old_size, -1)); - set_hash_hash (h, larger_vector (h->hash, new_size - old_size, -1)); + set_hash_key_and_value (h, larger_vector (h->key_and_value, + 2 * (new_size - old_size), 0)); + set_hash_next (h, larger_vector (h->next, new_size - old_size, 0)); + set_hash_hash (h, larger_vector (h->hash, new_size - old_size, 0)); set_hash_index (h, Fmake_vector (make_number (index_size), Qnil)); /* Update the free list. Do it so that new entries are added at In GNU Emacs 26.0.50.1 (x86_64-unknown-linux-gnu, X toolkit, Xaw3d scroll bars) of 2017-01-30 built on lechazo Repository revision: 5ddca31bf707686aafaf891c216702b64657c516 Windowing system distributor 'The X.Org Foundation', version 11.0.11900000 System Description: Debian GNU/Linux 9.0 (stretch) Recent messages: Wrote /home/monnier/src/emacs/work/src/fns.c Saving file /home/monnier/src/emacs/work/src/fns.c... Wrote /home/monnier/src/emacs/work/src/fns.c previous-line: Beginning of buffer [2 times] Hunk already applied Mark set Saving file /home/monnier/src/emacs/work/src/fns.c... Wrote /home/monnier/src/emacs/work/src/fns.c Saving file /home/monnier/src/emacs/work/src/fns.c... Wrote /home/monnier/src/emacs/work/src/fns.c Configured using: 'configure -C --enable-checking --enable-check-lisp-object-type 'CFLAGS=-Wall -g3 -Og -Wno-pointer-sign' PKG_CONFIG_PATH=/home/monnier/lib/pkgconfig' Configured features: XAW3D XPM JPEG TIFF GIF PNG SOUND GPM DBUS GSETTINGS NOTIFY GNUTLS LIBXML2 FREETYPE M17N_FLT LIBOTF XFT ZLIB TOOLKIT_SCROLL_BARS LUCID X11 Important settings: value of $LANG: fr_CH.UTF-8 locale-coding-system: utf-8-unix Major mode: InactiveMinibuffer Minor modes in effect: csv-field-index-mode: t diff-auto-refine-mode: t shell-dirtrack-mode: t electric-pair-mode: t global-reveal-mode: t reveal-mode: t auto-insert-mode: t savehist-mode: t minibuffer-electric-default-mode: t global-compact-docstrings-mode: t url-handler-mode: t global-eldoc-mode: t electric-indent-mode: t mouse-wheel-mode: t global-prettify-symbols-mode: t menu-bar-mode: t file-name-shadow-mode: t global-font-lock-mode: t auto-composition-mode: t auto-encryption-mode: t auto-compression-mode: t line-number-mode: t transient-mark-mode: t Load-path shadows: /home/monnier/src/emacs/elpa/packages/svg/svg hides /home/monnier/src/emacs/work/lisp/svg /home/monnier/src/emacs/elpa/packages/ada-mode/ada-xref hides /home/monnier/src/emacs/work/lisp/progmodes/ada-xref /home/monnier/src/emacs/elpa/packages/ada-mode/ada-stmt hides /home/monnier/src/emacs/work/lisp/progmodes/ada-stmt /home/monnier/src/emacs/elpa/packages/ada-mode/ada-prj hides /home/monnier/src/emacs/work/lisp/progmodes/ada-prj /home/monnier/src/emacs/elpa/packages/ada-mode/ada-mode hides /home/monnier/src/emacs/work/lisp/progmodes/ada-mode /home/monnier/src/emacs/elpa/packages/landmark/landmark hides /home/monnier/src/emacs/work/lisp/obsolete/landmark /home/monnier/src/emacs/elpa/packages/crisp/crisp hides /home/monnier/src/emacs/work/lisp/obsolete/crisp Features: (shadow mail-extr emacsbug message puny rfc822 mml mml-sec epa derived epg mm-decode mm-bodies mm-encode mail-parse rfc2231 mailabbrev gmm-utils mailheader sendmail grep csv-mode smerge-mode whitespace gud debug completion tar-mode dabbrev vc vc-dispatcher caml tuareg_indent tuareg caml-help caml-types caml-emacs map sm-c-mode smie ox-latex ox-icalendar ox-html ox-ascii ox-publish ox org-protocol org-mouse org-mobile org-agenda org-indent org-feed org-crypt org-capture org-attach org-id org-element org-rmail org-mhe org-irc org-info org-gnus gnus-util rmail rmail-loaddefs rfc2047 rfc2045 ietf-drums mm-util mail-prsvr mail-utils org-docview org-bibtex org-bbdb org-w3m org org-macro org-footnote org-pcomplete org-list org-faces org-entities org-version ob-emacs-lisp ob ob-tangle ob-ref ob-lob ob-table ob-exp org-src ob-keys ob-comint ob-core ob-eval org-compat org-macs org-loaddefs bibtex-style bibtex rect skeleton eieio-opt speedbar sb-image ezimage dframe find-func help-fns radix-tree html5-schema rng-xsd xsd-regexp rng-cmpct rng-nxml rng-valid rng-loc rng-uri rng-parse nxml-parse rng-match rng-dt rng-util rng-pttrn nxml-ns nxml-mode nxml-outln nxml-rap sgml-mode dom nxml-util nxml-enc xmltok sort mpc view cal-china lunar solar cal-dst cal-bahai cal-islam cal-hebrew holidays hol-loaddefs warnings cal-french diary-lib diary-loaddefs cal-move cal-menu calendar cal-loaddefs misearch multi-isearch cus-edit cus-start cus-load wid-edit autorevert filenotify doc-view subr-x jka-compr image-mode dired dired-loaddefs format-spec executable copyright vc-git diff-mode filecache reftex-dcr reftex reftex-loaddefs reftex-vars tex-mode compile shell pcomplete comint ansi-color ring latexenc server time-date noutline outline easy-mmode flyspell ispell checkdoc thingatpt load-dir elec-pair reveal autoinsert proof-site proof-autoloads cl pg-vars savehist minibuf-eldef disp-table compact-docstrings kotl-loaddefs advice info realgud-recursive-autoloads finder-inf url-auth package epg-config url-handlers url-parse auth-source eieio eieio-core cl-macs eieio-loaddefs password-cache url-vars seq byte-opt gv bytecomp byte-compile cl-extra help-mode easymenu cconv cl-loaddefs pcase cl-lib bbdb-loaddefs mule-util tooltip eldoc electric uniquify ediff-hook vc-hooks lisp-float-type mwheel term/x-win x-win term/common-win x-dnd tool-bar dnd fontset image regexp-opt fringe tabulated-list replace newcomment text-mode elisp-mode lisp-mode prog-mode register page menu-bar rfn-eshadow isearch timer select scroll-bar mouse jit-lock font-lock syntax font-core term/tty-colors frame cl-generic cham georgian utf-8-lang misc-lang vietnamese tibetan thai tai-viet lao korean japanese eucjp-ms cp51932 hebrew greek romanian slovak czech european ethiopic indian cyrillic chinese composite charscript case-table epa-hook jka-cmpr-hook help simple abbrev obarray minibuffer cl-preloaded nadvice loaddefs button faces cus-face macroexp files text-properties overlay sha1 md5 base64 format env code-pages mule custom widget hashtable-print-readable backquote dbusbind inotify dynamic-setting system-font-setting font-render-setting x-toolkit x multi-tty make-network-process emacs) Memory information: ((conses 8 523925 99482) (symbols 24 37808 0) (miscs 20 5334 863) (strings 16 112634 17461) (string-bytes 1 4377921) (vectors 8 68327) (vector-slots 4 2220644 87010) (floats 8 1387 1336) (intervals 28 30482 0) (buffers 520 88))