All of lore.kernel.org
 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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.