HashMapImpl should take into account m_deleteCount in its load factor and it should...
authorsbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 13 Sep 2016 00:14:59 +0000 (00:14 +0000)
committersbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 13 Sep 2016 00:14:59 +0000 (00:14 +0000)
commit6a3ef6b03bc4fd7ff7f32841ce9a47172fd98777
tree425af0f942839f5bb7cdf51e6f0028d93a43ed7a
parentfb84a89b4368b9232927293c22450327b6c58632
HashMapImpl should take into account m_deleteCount in its load factor and it should be able to rehash the table to be smaller
https://bugs.webkit.org/show_bug.cgi?id=161640

Reviewed by Geoffrey Garen.

JSTests:

* microbenchmarks/map-rehash.js: Added.
* stress/map-delete.js: Added.
(assert):
* stress/map-rehash-2.js: Added.
(assert):
* stress/map-rehash.js: Added.
(assert):

Source/JavaScriptCore:

HashMapImpl now takes into account m_deleteCount in its load factor.
It now knows how to rehash to either decrease its capacity, stay at
the same capacity, or increase its capacity. The reason we can sometimes
stay at the same capacity is that we can reduce the load factor enough
by rehashing that growing isn't warranted. The reason for this is that
anytime we rehash, we remove all deleted sentinels from the buffer.
Therefore, staying at the same same capacity, when there are deleted entries,
can still reduce the load factor because it removes all deleted sentinels.

* runtime/HashMapImpl.h:
(JSC::HashMapBuffer::create):
(JSC::HashMapBuffer::reset):
(JSC::HashMapImpl::HashMapImpl):
(JSC::HashMapImpl::add):
(JSC::HashMapImpl::remove):
(JSC::HashMapImpl::size):
(JSC::HashMapImpl::clear):
(JSC::HashMapImpl::approximateSize):
(JSC::HashMapImpl::shouldRehashAfterAdd):
(JSC::HashMapImpl::shouldShrink):
(JSC::HashMapImpl::rehash):
(JSC::HashMapImpl::checkConsistency):
(JSC::HashMapImpl::makeAndSetNewBuffer):
(JSC::HashMapImpl::assertBufferIsEmpty):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@205842 268f45cc-cd09-0410-ab3c-d52691b4dbfc
JSTests/ChangeLog
JSTests/microbenchmarks/map-rehash.js [new file with mode: 0644]
JSTests/stress/map-delete.js [new file with mode: 0644]
JSTests/stress/map-rehash-2.js [new file with mode: 0644]
JSTests/stress/map-rehash.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/runtime/HashMapImpl.h