Re: new `obarray` type

[Stefan Monnier <monnier@iro.umontreal.ca>]

> There are currently four uses of (make-vector LENGTH 0) in CC Mode, at
> least one of which, possibly two, genuinely deal with Lisp symbols.
> Converting those to hash-tables would probably be a net loss, though
> converting the ones which just use obarrays as a string look-up would
> surely gain.

I just tried such a conversion on all 4 uses.

The result isn't that bad, but indeed contrary to the EIEIO case, I get
a slight slow down (somewhat lost in the measurement noise, but still
a disappointment for me).  The culprit seems to be the use of cl-structs
instead of symbols in c-lang-constants (I can recover some of the speed
by adding (:type vector) (:named nil) to the defstruct definition).

In case you're interested in extracting the rest, find the patch below
(which was pretty thoroughly *un*tested),


        Stefan


diff --git a/lisp/progmodes/cc-defs.el b/lisp/progmodes/cc-defs.el
index 3fdd56124c..c4798c6108 100644
--- a/lisp/progmodes/cc-defs.el
+++ b/lisp/progmodes/cc-defs.el
@@ -2029,18 +2029,31 @@ c-add-language
     (error "Unknown base mode `%s'" base-mode))
   (put mode 'c-fallback-mode base-mode))
 
-(defvar c-lang-constants (make-vector 151 0))
-;;   Obarray used as a cache to keep track of the language constants.
+(defvar c-lang-constants (make-hash-table))
+;;   Hash-table used as a cache to keep track of the language constants.
 ;; The constants stored are those defined by `c-lang-defconst' and the values
 ;; computed by `c-lang-const'.  It's mostly used at compile time but it's not
 ;; stored in compiled files.
 
-;; The obarray contains all the language constants as symbols.  The
+;; The table contains all the language constants as `c-lang--const'.  The
 ;; value cells hold the evaluated values as alists where each car is
 ;; the mode name symbol and the corresponding cdr is the evaluated
 ;; value in that mode.  The property lists hold the source definitions
-;; and other miscellaneous data.  The obarray might also contain
-;; various other symbols, but those don't have any variable bindings.
+;; and other miscellaneous data.
+(defun c-lang--get-const (var)
+  (or (gethash var c-lang-constants)
+      (puthash var (c-lang--new-const) c-lang-constants)))
+(defun c-lang--forget-const (x) (remhash x c-lang-constants))
+(defun c-lang--map-const (f)
+  (maphash (lambda (sym _) (funcall f sym)) c-lang-constants))
+(cl-defstruct (c-lang--const
+	       ;; (:type vector) (:named nil)
+	       (:constructor c-lang--new-const ()))
+  (values nil :type alist)
+  dependents
+  source
+  documentation)
+
 
 (defvar c-lang-const-expansion nil)
 
@@ -2111,7 +2124,7 @@ c-lang-defconst
 earlier definition will not affect `c-lang-const' on the same
 constant.  A file is identified by its base name."
 
-  (let* ((sym (intern (symbol-name name) c-lang-constants))
+  (let* ((sym (c-lang--get-const name))
 	 ;; Make `c-lang-const' expand to a straightforward call to
 	 ;; `c-get-lang-constant' in `c--macroexpand-all' below.
 	 ;;
@@ -2139,7 +2152,7 @@ c-lang-defconst
       ;; The docstring is hardly used anywhere since there's no normal
       ;; symbol to attach it to.  It's primarily for getting the right
       ;; format in the source.
-      (put sym 'variable-documentation (car args))
+      (setf (c-lang--const-documentation sym) (car args))
       (setq args (cdr args)))
 
     (or args
@@ -2188,7 +2201,7 @@ c-lang-defconst
     ;; definitions for this symbol, to make sure the order in the
     ;; `source' property is correct even when files are loaded out of
     ;; order.
-    (setq pre-files (mapcar 'car (get sym 'source)))
+    (setq pre-files (mapcar #'car (c-lang--const-source sym)))
     (if (memq file pre-files)
 	;; This can happen when the source file (e.g. cc-langs.el) is first
 	;; loaded as source, setting a 'source property entry, and then itself
@@ -2210,8 +2223,8 @@ c-lang-defconst
 (defun c-define-lang-constant (name bindings &optional pre-files)
   ;; Used by `c-lang-defconst'.
 
-  (let* ((sym (intern (symbol-name name) c-lang-constants))
-	 (source (get sym 'source))
+  (let* ((sym (c-lang--get-const name))
+	 (source (c-lang--const-source sym))
 	 (file (intern
 		(or (c-get-current-file)
 		    (error "`c-lang-defconst' must be used in a file"))))
@@ -2228,28 +2241,28 @@ c-define-lang-constant
 	(unless (assq (car pre-files) source)
 	  (setq source (cons (list (car pre-files)) source)))
 	(setq pre-files (cdr pre-files)))
-      (put sym 'source (cons (setq elem (list file)) source)))
+      (setf (c-lang--const-source sym) (cons (setq elem (list file)) source)))
 
     (setcdr elem bindings)
 
-    ;; Bind the symbol as a variable, or clear any earlier evaluated
-    ;; value it has.
-    (set sym nil)
+    ;; Clear any earlier evaluated value it has.
+    (setf (c-lang--const-values sym) nil)
 
     ;; Clear the evaluated values that depend on this source.
-    (let ((agenda (get sym 'dependents))
-	  (visited (make-vector 101 0))
-	  ptr)
+    ;; NOTE: As far as I can tell, this code never does anything in
+    ;; "normal" use.  It's probably only used when loading a CC-mode
+    ;; version into an Emacs that already loaded another CC-mode version.
+    (let ((agenda (c-lang--const-dependents sym))
+	  ;; This is a set, implemented as a hash-table.
+	  ;; FIXME: Wouldn't a simple list be good enough?
+	  (visited (make-hash-table)))
       (while agenda
 	(setq sym (car agenda)
 	      agenda (cdr agenda))
-	(intern (symbol-name sym) visited)
-	(set sym nil)
-	(setq ptr (get sym 'dependents))
-	(while ptr
-	  (setq sym (car ptr)
-		ptr (cdr ptr))
-	  (unless (intern-soft (symbol-name sym) visited)
+	(puthash sym t visited)
+	(setf (c-lang--const-values sym) nil)
+	(dolist (sym (c-lang--const-dependents sym))
+	  (unless (gethash sym visited)
 	    (setq agenda (cons sym agenda))))))
 
     name))
@@ -2267,7 +2280,7 @@ c-lang-const
   (or (symbolp lang)
       (error "Not a symbol: %S" lang))
 
-  (let ((sym (intern (symbol-name name) c-lang-constants))
+  (let ((sym (c-lang--get-const name))
 	(mode (when lang (intern (concat (symbol-name lang) "-mode")))))
 
     (or (get mode 'c-mode-prefix) (null mode)
@@ -2293,7 +2306,7 @@ c-lang-const
 			     (if (eq file (car elem))
 				 nil	; Exclude our own file.
 			       (list (car elem))))
-			   (get sym 'source)))))
+			   (c-lang--const-source sym)))))
 
             ;; Make some effort to do a compact call to
             ;; `c-get-lang-constant' since it will be compiled in.
@@ -2336,8 +2349,8 @@ c-get-lang-constant
       (setq mode c-buffer-is-cc-mode)
       (error "No current language"))
 
-  (let* ((sym (intern (symbol-name name) c-lang-constants))
-	 (source (get sym 'source))
+  (let* ((sym (c-lang--get-const name))
+	 (source (c-lang--const-source sym))
 	 elem
 	 (eval-in-sym (and c-lang-constants-under-evaluation
 			   (caar c-lang-constants-under-evaluation))))
@@ -2345,8 +2358,7 @@ c-get-lang-constant
     ;; Record the dependencies between this symbol and the one we're
     ;; being evaluated in.
     (when eval-in-sym
-      (or (memq eval-in-sym (get sym 'dependents))
-	  (put sym 'dependents (cons eval-in-sym (get sym 'dependents)))))
+      (cl-pushnew eval-in-sym (c-lang--const-dependents sym)))
 
     ;; Make sure the source files have entries on the `source'
     ;; property so that loading will take place when necessary.
@@ -2361,8 +2373,7 @@ c-get-lang-constant
 	(set sym nil))
       (setq source-files (cdr source-files)))
 
-    (if (and (boundp sym)
-	     (setq elem (assq mode (symbol-value sym))))
+    (if (setq elem (assq mode (c-lang--const-values sym)))
 	(cdr elem)
 
       ;; Check if an evaluation of this symbol is already underway.
@@ -2418,10 +2429,10 @@ c-get-lang-constant
 	   ;; some caller higher up.
 	   (message "Eval error in the `c-lang-defconst' for `%S' in %s:"
 		    sym mode)
-	   (makunbound sym)
+	   (c-lang--forget-const name)
 	   (signal (car err) (cdr err))))
 
-	(set sym (cons (cons mode value) (symbol-value sym)))
+	(push (cons mode value) (c-lang--const-values sym))
 	value))))
 
 (defun c-find-assignment-for-mode (source-pos mode match-any-lang _name)
diff --git a/lisp/progmodes/cc-engine.el b/lisp/progmodes/cc-engine.el
index a5ade09791..abddbdf5bf 100644
--- a/lisp/progmodes/cc-engine.el
+++ b/lisp/progmodes/cc-engine.el
@@ -535,14 +535,14 @@ c-keyword-sym
   ;; Return non-nil if the string KEYWORD is a known keyword.  More
   ;; precisely, the value is the symbol for the keyword in
   ;; `c-keywords-obarray'.
-  (intern-soft keyword c-keywords-obarray))
+  (gethash keyword c-keywords-table))
 
 (defsubst c-keyword-member (keyword-sym lang-constant)
   ;; Return non-nil if the symbol KEYWORD-SYM, as returned by
   ;; `c-keyword-sym', is a member of LANG-CONSTANT, which is the name
   ;; of a language constant that ends with "-kwds".  If KEYWORD-SYM is
   ;; nil then the result is nil.
-  (get keyword-sym lang-constant))
+  (plist-get keyword-sym lang-constant))
 
 ;; String syntax chars, suitable for skip-syntax-(forward|backward).
 (defconst c-string-syntax (if (memq 'gen-string-delim c-emacs-features)
@@ -5991,7 +5991,8 @@ c-found-types
 
 (defsubst c-clear-found-types ()
   ;; Clears `c-found-types'.
-  (setq c-found-types (make-vector 53 0)))
+  ;; This is a set, implemented as a hash-table.
+  (setq c-found-types (make-hash-table :test #'equal)))
 
 (defun c-add-type (from to)
   ;; Add the given region as a type in `c-found-types'.  If the region
@@ -6005,31 +6006,30 @@ c-add-type
   ;;
   ;; This function might do hidden buffer changes.
   (let ((type (c-syntactic-content from to c-recognize-<>-arglists)))
-    (unless (intern-soft type c-found-types)
-      (unintern (substring type 0 -1) c-found-types)
-      (intern type c-found-types))))
+    (unless (gethash type c-found-types)
+      (remhash (substring type 0 -1) c-found-types)
+      (puthash type t c-found-types))))
 
 (defun c-unfind-type (name)
   ;; Remove the "NAME" from c-found-types, if present.
-  (unintern name c-found-types))
+  (remhash name c-found-types))
 
 (defsubst c-check-type (from to)
   ;; Return non-nil if the given region contains a type in
   ;; `c-found-types'.
   ;;
   ;; This function might do hidden buffer changes.
-  (intern-soft (c-syntactic-content from to c-recognize-<>-arglists)
-	       c-found-types))
+  (gethash (c-syntactic-content from to c-recognize-<>-arglists)
+	   c-found-types))
 
 (defun c-list-found-types ()
   ;; Return all the types in `c-found-types' as a sorted list of
   ;; strings.
   (let (type-list)
-    (mapatoms (lambda (type)
-		(setq type-list (cons (symbol-name type)
-				      type-list)))
-	      c-found-types)
-    (sort type-list 'string-lessp)))
+    (maphash (lambda (type _)
+		(push type type-list))
+	     c-found-types)
+    (sort type-list #'string-lessp)))
 
 ;; Shut up the byte compiler.
 (defvar c-maybe-stale-found-type)
diff --git a/lisp/progmodes/cc-langs.el b/lisp/progmodes/cc-langs.el
index 3b455fc090..8b6562f7df 100644
--- a/lisp/progmodes/cc-langs.el
+++ b/lisp/progmodes/cc-langs.el
@@ -164,13 +164,12 @@ c-lang-defvar
 	     (eq (car-safe val) 'c-lang-const)
 	     (eq (nth 1 val) var)
 	     (not (nth 2 val)))
-    ;; Special case: If there's no docstring and the value is a
-    ;; simple (c-lang-const foo) where foo is the same name as VAR
-    ;; then take the docstring from the language constant foo.
-    (setq doc (get (intern (symbol-name (nth 1 val)) c-lang-constants)
-		   'variable-documentation)))
-  (or (stringp doc)
-      (setq doc nil))
+      ;; Special case: If there's no docstring and the value is a
+      ;; simple (c-lang-const foo) where foo is the same name as VAR
+      ;; then take the docstring from the language constant foo.
+      (setq doc (c-lang--const-documentation (c-lang--get-const (nth 1 val)))))
+    (or (stringp doc)
+        (setq doc nil))
 
   (let ((elem (assq var (cdr c-lang-variable-inits))))
     (if elem
@@ -2700,13 +2699,12 @@ 'c-opt-op-identitier-prefix
   (defconst c-kwds-lang-consts
     ;; List of all the language constants that contain keyword lists.
     (let (list)
-      (mapatoms (lambda (sym)
-		  (when (and (boundp sym)
-			     (string-match "-kwds\\'" (symbol-name sym)))
-		    ;; Make the list of globally interned symbols
-		    ;; instead of ones interned in `c-lang-constants'.
-		    (setq list (cons (intern (symbol-name sym)) list))))
-		c-lang-constants)
+      (c-lang--map-const
+       (lambda (sym)
+	 (when (string-match "-kwds\\'" (symbol-name sym))
+	   ;; Make the list of globally interned symbols
+	   ;; instead of ones interned in `c-lang-constants'.
+	   (setq list (cons sym list)))))
       list)))
 
 (c-lang-defconst c-keywords
@@ -2749,8 +2747,8 @@ 'c-opt-op-identitier-prefix
 	    (setcdr elem (cons lang-const (cdr elem))))))
       result-alist))
 
-(c-lang-defvar c-keywords-obarray
-  ;; An obarray containing all keywords as symbols.  The property list
+(c-lang-defvar c-keywords-table
+  ;; A hash table containing all keywords as symbols.  The property list
   ;; of each symbol has a non-nil entry for the specific `*-kwds'
   ;; lists it's a member of.
   ;;
@@ -2767,22 +2765,23 @@ 'c-opt-op-identitier-prefix
 
   (let* ((alist (c-lang-const c-keyword-member-alist))
 	 kwd lang-const-list
-	 (obarray (make-vector (* (length alist) 2) 0)))
+	 (table (make-hash-table :test #'equal)))
     (while alist
       (setq kwd (caar alist)
 	    lang-const-list (cdar alist)
 	    alist (cdr alist))
-      (setplist (intern kwd obarray)
-		;; Emacs has an odd bug that causes `mapcan' to fail
-		;; with unintelligible errors.  (XEmacs works.)
-		;; (2015-06-24): This bug has not yet been fixed.
-		;;(mapcan (lambda (lang-const)
-		;;	      (list lang-const t))
-		;;	    lang-const-list)
-		(apply 'nconc (mapcar (lambda (lang-const)
+      (puthash kwd
+	       ;; Emacs has an odd bug that causes `mapcan' to fail
+	       ;; with unintelligible errors.  (XEmacs works.)
+	       ;; (2015-06-24): This bug has not yet been fixed.
+	       ;;(mapcan (lambda (lang-const)
+	       ;;	      (list lang-const t))
+	       ;;	    lang-const-list)
+	       (apply #'nconc (mapcar (lambda (lang-const)
 					(list lang-const t))
-				      lang-const-list))))
-    obarray))
+				      lang-const-list))
+	       table))
+    table))
 
 (c-lang-defconst c-regular-keywords-regexp
   ;; Adorned regexp matching all keywords that should be fontified