Wishlist.

It would be nice to have gensym live in subr.el or C for the utility of
having uniquely named uninterned symbols.  It is helpful, for instance,
in the readability of macroexpansions of pcase and other macros that
generate many uninterned symbols of the same name.

As far as C vs Elisp--cl-gensym is about 10x slower than make-symbol,
but as far as macroexpansion goes, I get the impression gensym is not a
big contributing factor. Consider the following:

(defmacro case-lambda (&rest spec)
  "Return an arbitrary arity function."
  (declare (indent 0) (debug (&rest (pcase-QPAT body))))
  (let ((args (make-symbol "args")))
   `(lambda (&rest ,args)
      (pcase-exhaustive ,args ,@spec))))

(benchmark-run-compiled 1000
  (macroexpand-all
   '(case-lambda
      (`() t)
      (`(,x) (cons x 1))
      (`(,x ,y) (list x y 2))
      (`(,x ,y . ,z) (pcase-lambda (`(,cat ,dog))
                       (vector cat dog x y z 8)))))

The difference between the benchmark with make-symbol and make-symbol
fset to gensym is less than 1% (looking at profiler samples, interval
set to 1us).

I wrote a naïve gensym in C that is only about 1.5x to 2x faster than
cl-gensym (and incompatible because of the inaccessible counter). Patch
attached.

I also attached a patch putting gensym into subr.el.

I've tested both patches.