Skip to content

SI-9513 decrement "deleted" count in OpenHashMap.put() when slot reused#4798

Merged
SethTisue merged 3 commits intoscala:2.11.xfrom
performantdata:issue/9513
Oct 15, 2015
Merged

SI-9513 decrement "deleted" count in OpenHashMap.put() when slot reused#4798
SethTisue merged 3 commits intoscala:2.11.xfrom
performantdata:issue/9513

Conversation

@performantdata
Copy link
Contributor

@performantdata performantdata commented Oct 10, 2015

No description provided.

@scala-jenkins scala-jenkins added this to the 2.11.8 milestone Oct 10, 2015
@performantdata
Copy link
Contributor Author

performantdata commented Oct 10, 2015

review @Ichoran

@performantdata
Copy link
Contributor Author

performantdata commented Oct 14, 2015

or @axel22 are you available for review?

Ichoran
Ichoran reviewed Oct 15, 2015
View reviewed changes
src/library/scala/collection/mutable/OpenHashMap.scala
Copy link
Contributor

@Ichoran Ichoran Oct 15, 2015

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

As long as you are making documentation changes, can you make the return type on growTable() explicit?

Copy link
Contributor Author

@performantdata performantdata Oct 15, 2015

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

One of my future PRs will touch growTable() code. I'll do it then. I only added the docs to help me parse the put() code.

Copy link
Contributor

@axel22 axel22 Oct 15, 2015

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I would also gently push for adding the explicit return type sooner rather than later, in case you make changes to this PR :)

Minor nitpick - we usually wrote docs like this in the past:

/** First line.
 *  Second line (star indented 1 whitespace).
 */

Copy link
Contributor Author

@performantdata performantdata Oct 15, 2015

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

in case you make changes to this PR

It's closed already. (But thanks for joining us!)

Minor nitpick

That's what Scala IDE wants to do to my code, too, but I'm just following the style guide. And the other style guide. Can't have too much style.

@Ichoran
Copy link
Contributor

Ichoran commented Oct 15, 2015

Just minor fixes; the core logic seems fine.

@retronym
Copy link
Member

retronym commented Oct 15, 2015

Thanks for spotting this!

Could you please expand the commit comment of 1fb32fc with some context for the change? I'm left wondering how the bug manifest itself: could it have resulted in incorrect answers from operations on a Map? Why does the test case need to peek into the internal state of the map rather than validate its behaviour?

@performantdata
Copy link
Contributor Author

performantdata commented Oct 15, 2015

Could you please expand the commit comment of 1fb32fc with some context for the change? I'm left wondering how the bug manifest itself

It's in the bug report. Is that not the place for it?

could it have resulted in incorrect answers from operations on a Map?

No.

Why does the test case need to peek into the internal state of the map rather than validate its behaviour?

There is no behavior externalized. There is no capacity() method available, for instance. Most I could do is pull in a library like JOL and measure object memory usage, which isn't quite as accurate. And @lrytz said this is kosher.

@retronym
Copy link
Member

retronym commented Oct 15, 2015

Sorry, I hadn't read the bug. I tend to repeat that information (what was wrong / how it manifest / what I'm changing / why this change is the right one) in the commit comment. Having it in Git makes life a little easier when we're on archaeological digs through the history. No need to do that for this PR, but keep it in mind for your next contribution.

@performantdata
Copy link
Contributor Author

performantdata commented Oct 15, 2015

I thought there was a way to make a reference like "SI-9513" in a GitHub commit message link back to the issue tracker. I've seen the other way in action, where JIRA hooks into the commits and links back to the VCS. But neither on this project.

Thinking about that more...we linked in-house instances of Subversion and JIRA, both ways.

@retronym
Copy link
Member

retronym commented Oct 15, 2015

I use a user script to add links from the GitHub UI to the corresponding JIRA issue. We disabled the automated links from JIRA tickets to GitHub PRs as we didn't like the way that that JIRA plugin automatically closed all tickets that were mentioned in the commit comments.

Here's an recent example of how I tend to structure a commit comment: f5dc96b

But in any case this change:

LGTM

SethTisue added a commit that referenced this pull request Oct 15, 2015
@SethTisue
Merge pull request #4798 from performantdata/issue/9513
fe76232 
SI-9513 decrement "deleted" count in OpenHashMap.put() when slot reused
@SethTisue SethTisue merged commit fe76232 into scala:2.11.x Oct 15, 2015
@SethTisue
Copy link
Member

SethTisue commented Oct 15, 2015

thank you @performantdata! much appreciated

@performantdata performantdata deleted the issue/9513 branch October 15, 2015 14:34
axel22
axel22 reviewed Oct 15, 2015
View reviewed changes
src/library/scala/collection/mutable/OpenHashMap.scala
Copy link
Contributor

@axel22 axel22 Oct 15, 2015

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Judging from the while loop, the returned index will either be such that table(index) == null or table(index).key == key. To avoid confusion, I would write:

 *  that either is empty, or is occupied by an entry with the given key.

(the "was" part requires context to understand, so I suggest to remove it)

Copy link
Contributor

@Ichoran Ichoran Oct 15, 2015

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

No, "is or was" is correct and crucial to understanding what the routine does, which is to return the entry which might have Some(value) or might have None for the value meaning that it was deleted. Hence "is or was". Maybe it needs to be expanded to make that logic clear.

Copy link
Contributor

@axel22 axel22 Oct 15, 2015

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yes, that was my point - it would help to expand it, because understanding "or was" required scanning through the entire class.

Copy link
Contributor Author

@performantdata performantdata Oct 15, 2015

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yes, there's undocumented semantics in the internal structure. I'm not trying to document everything (like it should have been when created), because I have other changes in mind that will remove said structure.

@performantdata
Copy link
Contributor Author

performantdata commented Oct 15, 2015

@Ichoran @axel22 SI-9520 may interest you too.

@SethTisue SethTisue mentioned this pull request Oct 16, 2015
Merged
SethTisue added a commit to SethTisue/scala that referenced this pull request Oct 16, 2015
@SethTisue
Merge commit 'ae5f0de' into merge-2.11-to-2.12-oct-16
a98e7d0 
rather than attempt to resolve merge conflicts in the Eclipse config,
the log shows that I merged ae5f0de with `-s ours`. (I have invited
Mike/performantdata to submit a followup PR bringing the Eclipse stuff
into a good state on 2.12.x.)

there were no other merge conflicts.

in test/junit/scala/collection/mutable/OpenHashMapTest.scala I had to
make the following change to fix a test failure:
-    val field = m.getClass.getDeclaredField("scala$collection$mutable$OpenHashMap$$deleted")
+    val field = m.getClass.getDeclaredField("deleted")

% git log --decorate --oneline -1 origin/2.11.x | cat
ae5f0de (origin/HEAD, origin/2.11.x) Merge pull request scala#4791 from performantdata/issue/9508
% git log --decorate --oneline -1 origin/2.12.x | cat
c99e53e (HEAD -> 2.12.x, origin/2.12.x) Merge pull request scala#4797 from lrytz/M3-versions
% export MB=$(git merge-base 2.12.x origin/2.11.x)
% echo $MB
42cafa2
% git checkout -b merge-2.11-to-2.12-oct-16
Switched to a new branch 'merge-2.11-to-2.12-oct-16'
% git log --graph --oneline --decorate $MB...origin/2.11.x | cat
*   ae5f0de (origin/HEAD, origin/2.11.x) Merge pull request scala#4791 from performantdata/issue/9508
|\
| * 08dca37 (origin/pull/4791) SI-9508 fix classpaths in Eclipse configuration
* |   fe76232 Merge pull request scala#4798 from performantdata/issue/9513
|\ \
| * | 9c97a7f (origin/pull/4798) Suppress unneeded import.
| * | 30d704d Document some OpenHashMap internal methods.
| * | 1fb32fc SI-9513 decrement "deleted" count in OpenHashMap.put() when slot reused
| |/
* |   14f875c Merge pull request scala#4788 from dk14/patch-1
|\ \
| * | 42acd55 (origin/pull/4788) explicitly specify insertion-order feature in docs
|  /
* |   68ce049 Merge pull request scala#4771 from som-snytt/issue/9492-here
|\ \
| * | f290962 (origin/pull/4771) SI-9492 Line trimming paste
| * | bc3589d SI-9492 REPL paste here doc
|  /
* |   9834fc8 Merge pull request scala#4610 from todesking/spec-implicits-remove-obsolete
|\ \
| * | 46009b1 (origin/pull/4610) Add view/context-bound parameter ordering rule
| * | 6eba305 Spec: Implicit parameters with context/view bound is allowed since 2.10
|  /
* |   d792e35 Merge pull request scala#4789 from janekdb/2.11.x-param-names-predicates-operations
|\ \
| |/
|/|
| * b19a07e (origin/pull/4789) Rename forall, exists and find predicate and operator params.
|/
*   648c7a1 Merge pull request scala#4790 from SethTisue/issue/9501
|\
| * 40d12f1 (origin/pull/4790) SI-9501 link README to Scala Hacker Guide
* e0b5891 Merge pull request scala#4786 from performantdata/issue/9506
* 39acad8 (origin/pull/4786) SI-9506 suppress Scala IDE-generated files in the Eclipse project dirs
* 74dc364 SI-9506 suppress Scala IDE-generated files in the Eclipse project dirs
% git merge fe76232
Auto-merging src/repl/scala/tools/nsc/interpreter/ILoop.scala
Auto-merging src/library/scala/util/Either.scala
Auto-merging src/library/scala/runtime/Tuple3Zipped.scala
Auto-merging src/library/scala/runtime/Tuple2Zipped.scala
Auto-merging src/library/scala/collection/parallel/ParIterableLike.scala
Auto-merging src/library/scala/collection/immutable/ListMap.scala
Auto-merging src/library/scala/collection/TraversableLike.scala
Auto-merging README.md
Merge made by the 'recursive' strategy.
 README.md                                                   | 11 +++++++-
 spec/07-implicits.md                                        | 12 +++++++--
 src/eclipse/interactive/.gitignore                          |  2 ++
 src/eclipse/partest/.gitignore                              |  2 ++
 src/eclipse/reflect/.gitignore                              |  2 ++
 src/eclipse/repl/.gitignore                                 |  2 ++
 src/eclipse/scala-compiler/.gitignore                       |  2 ++
 src/eclipse/scala-library/.gitignore                        |  2 ++
 src/eclipse/scaladoc/.gitignore                             |  2 ++
 src/eclipse/scalap/.gitignore                               |  2 ++
 src/eclipse/test-junit/.gitignore                           |  2 ++
 src/library/scala/collection/GenTraversableOnce.scala       | 23 ++++++++++++++---
 src/library/scala/collection/TraversableLike.scala          |  2 +-
 src/library/scala/collection/immutable/ListMap.scala        |  2 +-
 src/library/scala/collection/immutable/RedBlackTree.scala   |  4 +--
 src/library/scala/collection/immutable/Set.scala            | 74 ++++++++++++++++++++++++++---------------------------
 src/library/scala/collection/mutable/OpenHashMap.scala      | 19 +++++++++++++-
 src/library/scala/collection/parallel/ParIterableLike.scala | 18 ++++++-------
 src/library/scala/runtime/Tuple2Zipped.scala                |  8 +++---
 src/library/scala/runtime/Tuple3Zipped.scala                |  8 +++---
 src/library/scala/util/Either.scala                         | 12 ++++-----
 src/repl/scala/tools/nsc/interpreter/ILoop.scala            | 51 ++++++++++++++++++++++++------------
 src/repl/scala/tools/nsc/interpreter/ReplProps.scala        |  2 ++
 test/files/run/repl-paste-5.check                           | 28 ++++++++++++++++++++
 test/files/run/repl-paste-5.scala                           | 18 +++++++++++++
 test/junit/scala/collection/mutable/OpenHashMapTest.scala   | 42 ++++++++++++++++++++++++++++++
 26 files changed, 264 insertions(+), 88 deletions(-)
 create mode 100644 src/eclipse/interactive/.gitignore
 create mode 100644 src/eclipse/partest/.gitignore
 create mode 100644 src/eclipse/reflect/.gitignore
 create mode 100644 src/eclipse/repl/.gitignore
 create mode 100644 src/eclipse/scala-compiler/.gitignore
 create mode 100644 src/eclipse/scala-library/.gitignore
 create mode 100644 src/eclipse/scaladoc/.gitignore
 create mode 100644 src/eclipse/scalap/.gitignore
 create mode 100644 src/eclipse/test-junit/.gitignore
 create mode 100644 test/files/run/repl-paste-5.check
 create mode 100644 test/files/run/repl-paste-5.scala
 create mode 100644 test/junit/scala/collection/mutable/OpenHashMapTest.scala
% git merge -s ours ae5f0de
Merge made by the 'ours' strategy.
SethTisue added a commit to SethTisue/scala that referenced this pull request Oct 16, 2015
@SethTisue
% git log --decorate --oneline -1 origin/2.11.x | cat
5dc035f 
ae5f0de (origin/HEAD, origin/2.11.x) Merge pull request scala#4791 from performantdata/issue/9508
% git log --decorate --oneline -1 origin/2.12.x | cat
c99e53e (HEAD -> 2.12.x, origin/2.12.x) Merge pull request scala#4797 from lrytz/M3-versions
% export MB=$(git merge-base 2.12.x origin/2.11.x)
% echo $MB
42cafa2
% git log --graph --oneline --decorate $MB...origin/2.11.x | cat
*   ae5f0de (origin/HEAD, origin/2.11.x) Merge pull request scala#4791 from performantdata/issue/9508
|\
| * 08dca37 (origin/pull/4791) SI-9508 fix classpaths in Eclipse configuration
* |   fe76232 Merge pull request scala#4798 from performantdata/issue/9513
|\ \
| * | 9c97a7f (origin/pull/4798) Suppress unneeded import.
| * | 30d704d Document some OpenHashMap internal methods.
| * | 1fb32fc SI-9513 decrement "deleted" count in OpenHashMap.put() when slot reused
| |/
* |   14f875c Merge pull request scala#4788 from dk14/patch-1
|\ \
| * | 42acd55 (origin/pull/4788) explicitly specify insertion-order feature in docs
|  /
* |   68ce049 Merge pull request scala#4771 from som-snytt/issue/9492-here
|\ \
| * | f290962 (origin/pull/4771) SI-9492 Line trimming paste
| * | bc3589d SI-9492 REPL paste here doc
|  /
* |   9834fc8 Merge pull request scala#4610 from todesking/spec-implicits-remove-obsolete
|\ \
| * | 46009b1 (origin/pull/4610) Add view/context-bound parameter ordering rule
| * | 6eba305 Spec: Implicit parameters with context/view bound is allowed since 2.10
|  /
* |   d792e35 Merge pull request scala#4789 from janekdb/2.11.x-param-names-predicates-operations
|\ \
| |/
|/|
| * b19a07e (origin/pull/4789) Rename forall, exists and find predicate and operator params.
|/
*   648c7a1 Merge pull request scala#4790 from SethTisue/issue/9501
|\
| * 40d12f1 (origin/pull/4790) SI-9501 link README to Scala Hacker Guide
* e0b5891 Merge pull request scala#4786 from performantdata/issue/9506
* 39acad8 (origin/pull/4786) SI-9506 suppress Scala IDE-generated files in the Eclipse project dirs
* 74dc364 SI-9506 suppress Scala IDE-generated files in the Eclipse project dirs
% git merge ae5f0de
Auto-merging src/repl/scala/tools/nsc/interpreter/ILoop.scala
Auto-merging src/library/scala/util/Either.scala
Auto-merging src/library/scala/runtime/Tuple3Zipped.scala
Auto-merging src/library/scala/runtime/Tuple2Zipped.scala
Auto-merging src/library/scala/collection/parallel/ParIterableLike.scala
Auto-merging src/library/scala/collection/immutable/ListMap.scala
Auto-merging src/library/scala/collection/TraversableLike.scala
Auto-merging src/eclipse/test-junit/.classpath
CONFLICT (content): Merge conflict in src/eclipse/test-junit/.classpath
Auto-merging src/eclipse/scaladoc/.classpath
CONFLICT (content): Merge conflict in src/eclipse/scaladoc/.classpath
Auto-merging src/eclipse/scala-compiler/.classpath
Auto-merging src/eclipse/repl/.classpath
CONFLICT (content): Merge conflict in src/eclipse/repl/.classpath
Auto-merging src/eclipse/partest/.classpath
CONFLICT (content): Merge conflict in src/eclipse/partest/.classpath
Auto-merging src/eclipse/interactive/.classpath
Auto-merging README.md
Automatic merge failed; fix conflicts and then commit the result.
% git checkout --ours src/eclipse/partest/.classpath
% git checkout --ours src/eclipse/repl/.classpath
% git checkout --ours src/eclipse/scaladoc/.classpath
% git checkout --ours src/eclipse/test-junit/.classpath
% git add -u
% emacs test/junit/scala/collection/mutable/OpenHashMapTest.scala
% git diff test/junit/scala/collection/mutable/OpenHashMapTest.scala | cat
...
-    val field = m.getClass.getDeclaredField("scala$collection$mutable$OpenHashMap$$deleted")
+    val field = m.getClass.getDeclaredField("deleted")
...
% git add -u
SethTisue added a commit to SethTisue/scala that referenced this pull request Oct 16, 2015
@SethTisue
merge 2.11.x onto 2.12.x, Oct 16 2015
3141fdd 
there were merge conflicts in the Eclipse config that I resolved with
--ours.  I invite @performantdata to submit a followup PR bringing the
Eclipse stuff into a good state on 2.12.x.

there was a test failure in
test/junit/scala/collection/mutable/OpenHashMapTest.scala
due to the 2.12 compiler emitting the field backing a
private var differently (with an unmangled name).  Lukas
says the difference is expected, so I just updated the
code in the test.

there were no other merge conflicts.

% git log --decorate --oneline -1 origin/2.11.x | cat
ae5f0de (origin/HEAD, origin/2.11.x) Merge pull request scala#4791 from performantdata/issue/9508
% git log --decorate --oneline -1 origin/2.12.x | cat
c99e53e (HEAD -> 2.12.x, origin/2.12.x) Merge pull request scala#4797 from lrytz/M3-versions
% export MB=$(git merge-base 2.12.x origin/2.11.x)
% echo $MB
42cafa2
% git log --graph --oneline --decorate $MB...origin/2.11.x | cat
*   ae5f0de (origin/HEAD, origin/2.11.x) Merge pull request scala#4791 from performantdata/issue/9508
|\
| * 08dca37 (origin/pull/4791) SI-9508 fix classpaths in Eclipse configuration
* |   fe76232 Merge pull request scala#4798 from performantdata/issue/9513
|\ \
| * | 9c97a7f (origin/pull/4798) Suppress unneeded import.
| * | 30d704d Document some OpenHashMap internal methods.
| * | 1fb32fc SI-9513 decrement "deleted" count in OpenHashMap.put() when slot reused
| |/
* |   14f875c Merge pull request scala#4788 from dk14/patch-1
|\ \
| * | 42acd55 (origin/pull/4788) explicitly specify insertion-order feature in docs
|  /
* |   68ce049 Merge pull request scala#4771 from som-snytt/issue/9492-here
|\ \
| * | f290962 (origin/pull/4771) SI-9492 Line trimming paste
| * | bc3589d SI-9492 REPL paste here doc
|  /
* |   9834fc8 Merge pull request scala#4610 from todesking/spec-implicits-remove-obsolete
|\ \
| * | 46009b1 (origin/pull/4610) Add view/context-bound parameter ordering rule
| * | 6eba305 Spec: Implicit parameters with context/view bound is allowed since 2.10
|  /
* |   d792e35 Merge pull request scala#4789 from janekdb/2.11.x-param-names-predicates-operations
|\ \
| |/
|/|
| * b19a07e (origin/pull/4789) Rename forall, exists and find predicate and operator params.
|/
*   648c7a1 Merge pull request scala#4790 from SethTisue/issue/9501
|\
| * 40d12f1 (origin/pull/4790) SI-9501 link README to Scala Hacker Guide
* e0b5891 Merge pull request scala#4786 from performantdata/issue/9506
* 39acad8 (origin/pull/4786) SI-9506 suppress Scala IDE-generated files in the Eclipse project dirs
* 74dc364 SI-9506 suppress Scala IDE-generated files in the Eclipse project dirs
% git merge ae5f0de
Auto-merging src/repl/scala/tools/nsc/interpreter/ILoop.scala
Auto-merging src/library/scala/util/Either.scala
Auto-merging src/library/scala/runtime/Tuple3Zipped.scala
Auto-merging src/library/scala/runtime/Tuple2Zipped.scala
Auto-merging src/library/scala/collection/parallel/ParIterableLike.scala
Auto-merging src/library/scala/collection/immutable/ListMap.scala
Auto-merging src/library/scala/collection/TraversableLike.scala
Auto-merging src/eclipse/test-junit/.classpath
CONFLICT (content): Merge conflict in src/eclipse/test-junit/.classpath
Auto-merging src/eclipse/scaladoc/.classpath
CONFLICT (content): Merge conflict in src/eclipse/scaladoc/.classpath
Auto-merging src/eclipse/scala-compiler/.classpath
Auto-merging src/eclipse/repl/.classpath
CONFLICT (content): Merge conflict in src/eclipse/repl/.classpath
Auto-merging src/eclipse/partest/.classpath
CONFLICT (content): Merge conflict in src/eclipse/partest/.classpath
Auto-merging src/eclipse/interactive/.classpath
Auto-merging README.md
Automatic merge failed; fix conflicts and then commit the result.
% git checkout --ours src/eclipse/partest/.classpath
% git checkout --ours src/eclipse/repl/.classpath
% git checkout --ours src/eclipse/scaladoc/.classpath
% git checkout --ours src/eclipse/test-junit/.classpath
% git add -u
% emacs test/junit/scala/collection/mutable/OpenHashMapTest.scala
% git diff test/junit/scala/collection/mutable/OpenHashMapTest.scala | cat
...
-    val field = m.getClass.getDeclaredField("scala$collection$mutable$OpenHashMap$$deleted")
+    val field = m.getClass.getDeclaredField("deleted")
...
% git add -u
@scabug scabug mentioned this pull request Apr 7, 2017
Closed
@scabug scabug mentioned this pull request Apr 24, 2017
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

2.11.8

Development

Successfully merging this pull request may close these issues.

6 participants

@performantdata @Ichoran @retronym @SethTisue @axel22 @scala-jenkins