This is an enhancement request for Emacs 25.2.

When many markers are created but not explicitly made to point to no
buffer after use, GC performance suffers severely. (Normal performance
(apparently) suffers a little. That's okay and I don't consider that a
problem.)  An automated test script that was in no way explicitly
designed to do so caused an Emacs session to be caught in garbage
collection for more than an hour.

The problem can be observed with this test code:
----------
(defvar l2 nil)

(defun loop (lim)
  (let ((i 0)
        (l nil))
    (while (< i lim)
      (push (copy-marker (point-max)) l)
      (push (copy-marker (point-min)) l)
      (push (copy-marker (point-max)) l2)
      (push (copy-marker (point-min)) l2)
      (setq i (1+ i)))))
----------

On this system, I'm seeing the following behaviour:

----------
$ time emacs -Q --load ~/git/ankol/emacs/loop.el --eval '(loop 10000)'
--eval '(garbage-collect)' --kill

real    0m2.556s
user    0m2.392s
sys    0m0.068s

$ time emacs -Q --load ~/git/ankol/emacs/loop.el --eval '(loop 20000)'
--eval '(garbage-collect)' --kill

real    0m19.576s
user    0m19.340s
sys    0m0.068s
----------

Upon investigation, it turns out that we keep a buffer's markers in a
singly-linked list, which we walk for every marker as it is
collected. That's O(n^2) (where n is the number of collected markers,
not that of markers that survive this garbage collection cycle); if
Emacs is made to grow to considerable size, this begins to dominate and
the hour-long GC problem appears.

This happened to me while testing a new programming language mode that
has a number of interactive commands that transform code without
changing its semantics; in order to make sure the transformations
weren't doing anything wrong, I ran them automatedly in large numbers,
and that's when my test sessions would appear to freeze while caught in
GC.

I thought it would be very easy to modify the code to avoid the problem;
it was a bit harder than I thought, because the GC mark bit is not
equivalent to "this object survives the current GC cycle". In the
attached patch, I ended up sacrificing one more bit to mean precisely
that, so we can walk a buffer's marker list once and unchain all
collected markers. If there's a better way of telling whether a marker
is due to be collected in the current GC cycle, I'd be happy to modify
the code.  (I tried mem_find and PURE_P, but there appear to be some
additional cases that are missed by that approach.)

As always, the patch is merely a suggestion.  However, it improves
performance (of the test code above and the actual test case) so
drastically that I think it is a good idea to fix this problem.

In GNU Emacs 25.2.50.19 (x86_64-pc-linux-gnu, X toolkit, Xaw scroll bars)
 of 2016-09-26 built on amygdala
Repository revision: 5ee56c4613e9380dbbe4bbaa97b29dd377e2134c
Windowing system distributor 'The X.Org Foundation', version 11.0.11804000
System Description:    Debian GNU/Linux unstable (sid)

Recent messages:
For information about GNU Emacs and the GNU system, type C-h C-a.

Configured features:
XPM JPEG TIFF GIF PNG SOUND DBUS GSETTINGS NOTIFY GNUTLS LIBXML2
FREETYPE XFT ZLIB TOOLKIT_SCROLL_BARS LUCID X11

Important settings:
  value of $LANG: en_US.UTF-8
  locale-coding-system: utf-8-unix

Major mode: Lisp Interaction

Minor modes in effect:
  tooltip-mode: t
  global-eldoc-mode: t
  electric-indent-mode: t
  mouse-wheel-mode: t
  tool-bar-mode: t
  menu-bar-mode: t
  file-name-shadow-mode: t
  global-font-lock-mode: t
  font-lock-mode: t
  blink-cursor-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:
None found.

Features:
(shadow sort mail-extr emacsbug message subr-x puny seq byte-opt gv
bytecomp byte-compile cl-extra help-mode cconv cl-loaddefs pcase cl-lib
dired dired-loaddefs format-spec rfc822 mml easymenu mml-sec
password-cache epa derived epg epg-config gnus-util rmail rmail-loaddefs
mm-decode mm-bodies mm-encode mail-parse rfc2231 mailabbrev gmm-utils
mailheader sendmail rfc2047 rfc2045 ietf-drums mm-util mail-prsvr
mail-utils time-date 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 newcomment elisp-mode lisp-mode prog-mode register page
menu-bar rfn-eshadow timer select scroll-bar mouse jit-lock font-lock
syntax facemenu 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 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 16 96543 9103)
 (symbols 48 20425 0)
 (miscs 40 47 168)
 (strings 32 18288 5117)
 (string-bytes 1 571191)
 (vectors 16 13407)
 (vector-slots 8 447852 3741)
 (floats 8 185 69)
 (intervals 56 221 0)
 (buffers 976 11))