qemu-devel.nongnu.org archive mirror
 help / color / mirror / Atom feed
* [Qemu-devel] [PATCH v5 00/18] tb hash improvements
@ 2016-05-14  3:34 Emilio G. Cota
  2016-05-14  3:34 ` [Qemu-devel] [PATCH v5 01/18] compiler.h: add QEMU_ALIGNED() to enforce struct alignment Emilio G. Cota
                   ` (18 more replies)
  0 siblings, 19 replies; 79+ messages in thread
From: Emilio G. Cota @ 2016-05-14  3:34 UTC (permalink / raw)
  To: QEMU Developers, MTTCG Devel
  Cc: Alex Bennée, Paolo Bonzini, Peter Crosthwaite,
	Richard Henderson, Sergey Fedorov

This patchset applies on top of tcg-next (8b1fe3f4 "cpu-exec:
Clean up 'interrupt_request' reloading", tagged "pull-tcg-20160512").

For reference, here is v4:
  https://lists.gnu.org/archive/html/qemu-devel/2016-04/msg04670.html

Changes from v4:

- atomics.h:
  + Add atomic_read_acquire and atomic_set_release
  + Rename atomic_test_and_set to atomic_test_and_set_acquire
  [ Richard: I removed your reviewed-by ]

- qemu_spin @ thread.h:
  + add bool qemu_spin_locked() to check whether the lock is taken.
  + Use newly-added acquire/release atomic ops. This is clearer and
    improves performance; for instance, now we don't emit an
    unnecessary smp_mb() thanks to using atomic_set_release()
    instead of atomic_mb_set(). Also, note that __sync_test_and_set
    has acquire semantics, so it makes sense to have an
    atomic_test_and_set_acquire that directly calls it, instead
    of calling atomic_xchg, which emits a full barrier (that we don't
    need) before __sync_test_and_set.
  [ Richard: I removed your reviewed-by ]

- tests:
  + add parallel benchmark (qht-bench). Some perf numbers in
    the commit message, comparing QHT vs. CLHT and ck_hs.

  + invoke qht-bench from `make check` with test-qht-par. It
    uses system(3); I couldn't find a way to detect from qht-bench
    when it is run from gtester, so I decided to just add a silly
    program to invoke it.

- trivial: util/Makefile.objs: add qdist.o and qht.o each on a
           separate line

- trivial: added copyright header to test programs

- trivial: updated phys_pc, pc, flags commit message with Richard's
           comment that hashing cs_base probably isn't worth it.

- qht:
  + Document that duplicate pointer values cannot be inserted.
  + qht_insert: return true/false upon success/failure, just like
                qht_remove. This can help find bugs.
  + qht_remove: only write to seqlock if the removal happens --
                otherwise the write is unnecessary, since nothing
		is written to the bucket.
  + trivial: s/n_items/n_entries/ for consistency.
  + qht_grow: substitute it for qht_resize. This is mostly useful
              for testing.
  + resize: do not track qht_map->n_entries; track instead the
            number of non-head buckets added.
	    This improves scalability, since we only increment
	    this number (with the relatively expensive atomic_inc)
	    every time a new non-head bucket is allocated, instead
	    of every time an entry is added/removed.
    * return bool from qht_resize and qht_reset_size; they return
      false if the resize was not needed (i.e. if the previous size
      was the requested size).
  + qht_lookup: do not check for !NULL entries; check directly
                for a hash match.
		This gives a ~2% perf. increase during
		benchmarking. The buckets in the microbenchmarks
		are equally-sized well distributed, which is
		approximately the case in QEMU thanks to xxhash
		and resizing.
  + Remove MRU bucket promotion policy. With automatic resizing,
    this is not needed. Furthermore, removing it saves code.
  + qht_lookup: Add fast-path without do {} while (seqlock). This
                gives a 4% perf. improvement on a read-only benchmark.
  + struct qht_bucket: document the struct
  + rename qht_lock() to qht_map_lock_buckets()
  + add map__atomic_mb and bucket_next__atomic_mb helpers that
    include the necessary atomic_read() and rmb().

  [ All the above changes for qht are simple enough that I kept
    Richard's reviewed-by.]

  + Support concurrent writes to separate buckets. This is in an
    additional patch to ease reviewing; feel free to squash it on
    top of the QHT patch.

Thanks,

		Emilio

^ permalink raw reply	[flat|nested] 79+ messages in thread

end of thread, other threads:[~2016-05-25  0:10 UTC | newest]

Thread overview: 79+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2016-05-14  3:34 [Qemu-devel] [PATCH v5 00/18] tb hash improvements Emilio G. Cota
2016-05-14  3:34 ` [Qemu-devel] [PATCH v5 01/18] compiler.h: add QEMU_ALIGNED() to enforce struct alignment Emilio G. Cota
2016-05-14  3:34 ` [Qemu-devel] [PATCH v5 02/18] seqlock: remove optional mutex Emilio G. Cota
2016-05-14  3:34 ` [Qemu-devel] [PATCH v5 03/18] seqlock: rename write_lock/unlock to write_begin/end Emilio G. Cota
2016-05-14  3:34 ` [Qemu-devel] [PATCH v5 04/18] include/processor.h: define cpu_relax() Emilio G. Cota
2016-05-18 17:47   ` Sergey Fedorov
2016-05-18 18:29     ` Emilio G. Cota
2016-05-18 18:37       ` Sergey Fedorov
2016-05-14  3:34 ` [Qemu-devel] [PATCH v5 05/18] atomics: add atomic_test_and_set_acquire Emilio G. Cota
2016-05-16 10:05   ` Paolo Bonzini
2016-05-17 16:15   ` Sergey Fedorov
2016-05-17 16:23     ` Paolo Bonzini
2016-05-17 16:47       ` Sergey Fedorov
2016-05-17 17:08         ` Paolo Bonzini
2016-05-14  3:34 ` [Qemu-devel] [PATCH v5 06/18] atomics: add atomic_read_acquire and atomic_set_release Emilio G. Cota
2016-05-15 10:22   ` Pranith Kumar
2016-05-16 18:27     ` Emilio G. Cota
2016-05-17 16:53   ` Sergey Fedorov
2016-05-17 17:08     ` Paolo Bonzini
2016-05-14  3:34 ` [Qemu-devel] [PATCH v5 07/18] qemu-thread: add simple test-and-set spinlock Emilio G. Cota
     [not found]   ` <573B5134.8060104@gmail.com>
2016-05-17 19:19     ` Richard Henderson
2016-05-17 19:57       ` Sergey Fedorov
2016-05-17 20:01         ` Sergey Fedorov
2016-05-17 22:12           ` Richard Henderson
2016-05-17 22:22             ` Richard Henderson
2016-05-17 20:04       ` Emilio G. Cota
2016-05-17 20:20         ` Sergey Fedorov
2016-05-18  0:28           ` Emilio G. Cota
2016-05-18 14:18             ` Sergey Fedorov
2016-05-18 14:47               ` Sergey Fedorov
2016-05-18 14:59                 ` Paolo Bonzini
2016-05-18 15:05                   ` Sergey Fedorov
2016-05-18 15:09                     ` Paolo Bonzini
2016-05-18 16:59                       ` Emilio G. Cota
2016-05-18 17:00                         ` Paolo Bonzini
2016-05-18 15:35                     ` Peter Maydell
2016-05-18 15:36                       ` Paolo Bonzini
2016-05-18 15:44                         ` Peter Maydell
2016-05-18 15:59                           ` Sergey Fedorov
2016-05-18 16:02                       ` Richard Henderson
2016-05-17 19:38     ` Emilio G. Cota
2016-05-17 20:35       ` Sergey Fedorov
2016-05-17 23:18         ` Emilio G. Cota
2016-05-18 13:59           ` Sergey Fedorov
2016-05-18 14:05             ` Paolo Bonzini
2016-05-18 14:10               ` Sergey Fedorov
2016-05-18 14:40                 ` Paolo Bonzini
2016-05-18 18:21   ` Sergey Fedorov
2016-05-18 19:04     ` Emilio G. Cota
2016-05-18 19:51   ` Sergey Fedorov
2016-05-18 20:52     ` Emilio G. Cota
2016-05-18 20:57       ` Sergey Fedorov
2016-05-14  3:34 ` [Qemu-devel] [PATCH v5 08/18] exec: add tb_hash_func5, derived from xxhash Emilio G. Cota
2016-05-17 17:22   ` Sergey Fedorov
2016-05-17 19:48     ` Emilio G. Cota
2016-05-14  3:34 ` [Qemu-devel] [PATCH v5 09/18] tb hash: hash phys_pc, pc, and flags with xxhash Emilio G. Cota
2016-05-17 17:47   ` Sergey Fedorov
2016-05-17 19:09     ` Emilio G. Cota
2016-05-14  3:34 ` [Qemu-devel] [PATCH v5 10/18] qdist: add module to represent frequency distributions of data Emilio G. Cota
2016-05-14  3:34 ` [Qemu-devel] [PATCH v5 11/18] qdist: add test program Emilio G. Cota
2016-05-14  3:34 ` [Qemu-devel] [PATCH v5 12/18] qht: QEMU's fast, resizable and scalable Hash Table Emilio G. Cota
2016-05-20 22:13   ` Sergey Fedorov
2016-05-21  2:48     ` Emilio G. Cota
2016-05-21 17:41       ` Emilio G. Cota
2016-05-22  8:01         ` Alex Bennée
2016-05-23  5:35           ` Emilio G. Cota
2016-05-21 20:07       ` Sergey Fedorov
2016-05-23 19:29       ` Sergey Fedorov
2016-05-14  3:34 ` [Qemu-devel] [PATCH v5 13/18] qht: support parallel writes Emilio G. Cota
2016-05-23 20:28   ` Sergey Fedorov
2016-05-24 22:07     ` Emilio G. Cota
2016-05-24 22:17       ` Sergey Fedorov
2016-05-25  0:10         ` Emilio G. Cota
2016-05-14  3:34 ` [Qemu-devel] [PATCH v5 14/18] qht: add test program Emilio G. Cota
2016-05-14  3:34 ` [Qemu-devel] [PATCH v5 15/18] qht: add qht-bench, a performance benchmark Emilio G. Cota
2016-05-14  3:34 ` [Qemu-devel] [PATCH v5 16/18] qht: add test-qht-par to invoke qht-bench from 'check' target Emilio G. Cota
2016-05-14  3:34 ` [Qemu-devel] [PATCH v5 17/18] tb hash: track translated blocks with qht Emilio G. Cota
2016-05-14  3:34 ` [Qemu-devel] [PATCH v5 18/18] translate-all: add tb hash bucket info to 'info jit' dump Emilio G. Cota
2016-05-23 22:26 ` [Qemu-devel] [PATCH v5 00/18] tb hash improvements Sergey Fedorov

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).