A Gist containing some naive benchmarks (together with the source code for them) is available here: https://gist.github.com/ruippeixotog/20f961055a94345ad24c2fd58079d26c

looks good otherwise. the build failure looks weird - let's just try again (amend your changes and git push -f).

@lrytz thanks for the review, I just fixed both of the details you mentioned. The build failure didn't look like it was due to the modifications of this PR; I can try rebasing this into the current master if it doesn't work.

I just rebased the branch on top of 2.12.x, but the error still occurs and Jenkins does not seem to be giving any helpful error messages. However, looking at the pull request list it seems that I'm the only one having this problem... Can anyone help me figuring out what's wrong with this PR?

I have one major concern about performance. I wasn't able to spot why the test is failing, though.

For the compilation failure, if I re-add .toList.reverseIterator to ListMap.iterator, compilation succeeds. This means that some part of the compiler (i guess the part checking forward references) depends on the current iteration order.

Honestly, when i started looking at this PR, I was very surprised to learn that "ListMap and ListSet doesn't seem to make any guarantees in terms of iteration (SI-8985)". I think this situation creates a lot of confusion, e.g., http://stackoverflow.com/questions/3481925/insertion-ordered-listset. Just like LinkedHashSet / LinkedHashMap for mutable collections, I think that ListSet / ListMap should guarantee that "all traversal methods of this class visit elements in the order they were inserted".

I was also surprised to see that ListMap and ListSet did not provide such guarantees - I always thought of them as an immutable alternative to LinkedHashMap and LinkedHashSet. If even the Scala compiler relies on their ordering, then I would rather make both ListMap and ListSet be insertion-ordered and document that properly in Scaladoc.

As you saw, iterating in the "correct" order requires the collection to be converted to a list and reversed, which has a performance hit. However, as @Ichoran mentioned, these collections are really only useful with a small number of elements, so I think it would be OK to do that.

The benchmarking you did isn't really reliable enough to do anything with. You should at least use Thyme; JMH would be better.

From this, it looks like you need to special-case 0-4. Having a 2x performance hit in the most commonly used cases doesn't justify the gain in the cases which the data structure isn't suited for anyway.

But I'd do some more robust benchmarking first.

Thanks for the framework suggestions! I benchmarked again ListMap using JMH. I also benchmarked ListSet. The full results are available here: ListMap, ListSet.

If I did not anything wrong in the benchmarks, it seems the custom builder is significantly slower for every size equal to or below 6... Considering again that the collection should only be used for very small sizes due to its overall performance, I don't think it's worth it to keep the custom builder and write special cases for small sizes.

If you take a look the test results, it seems that the custom ListSet builder is also significantly slower than the default one (a mutable.SetBuilder). It is expected, as the two collections are pretty much equal. Should I remove ListSetBuilder then?

My recommendation would be to remove ListSetBuilder if it's not an improvement.

Yes, I agree it's better that way. I have just pushed the updated commit.

OK, I agree the latest change looks good. A few small things to do:

• can you specify the iteration order in the scaladoc, similar to LinkedHashMap/Set?
• move the existing test case t3822.scala to the new junit test, so that they are all in the same place
• also t7445 could be moved to junit. actually, ListSet probably has the same bug, it was only fixed for ListMap -- can you check? the fix for ListMap was in SI-7445 ListMap.tail is returning wrong result #3388.
• method iterator first creates a List instance, then reverseIterator creates the reversed list instance. the following would only create one single list:

  def iterator: Iterator[(A,B)] = {
    def reverseList = {
      var self = this
      var res: List[(A, B)] = Nil
      while (!self.isEmpty) {
        res = (self.key, self.value) :: res
        self = self.next
      }
      res
    }
    reverseList.iterator
  }

in general, maybe do another pass over the two classes to bring the implementations closer together (rename ListMap.remove0 to removeInternal, replace ListSet.unchecked_outer by next, etc)

Sure, I'll move t7445.scala code to a junit test and I'll improve the iterator as you suggested (adding two new tests for that). ListSet is indeed affected by SI-7445; I'll also fix that.

t3822 is a test that becomes ridiculously slow when the custom builder is taken off (though the Jenkins build seems to have made it past that test)... Do we still want to keep it? SI-3822 is a very old issue and it involves an use case that we concluded here that was inadequate for that collection. Regardless of that, all ListMap/ListSet methods are now tail recursive, so the bug is fixed anyway.

Regarding the Scaladoc and the general revamp I was also thinking of doing that, as it's way easier to fix bugs and add improvement to those collections if their code is as similar as it could be (after all, its internal organization and algorithms associated are exactly the same). However, I believe it would be better if I did that either in a separate pull request or in a separate commit; otherwise, the bugs and improvements present in this PR would become much more difficult to track in the commit history later, as they would be concealed by a lot of method renames and code moves. What do you think? Is there a problem if this PR has multiple commits?

t3822 is a test that becomes ridiculously slow

Right, I agree we can get rid of it.

Is there a problem if this PR has multiple commits?

No, this is common practice in the scala repo. I agree that having separate commits for refactorings, scaladoc and bugfixes makes a lot of sense.

involves an use case that we concluded here that was inadequate for that collection

Can you make sure to include that in the Scaladoc cleanup? All operations are O(n) (right?), including the creation of a ListSet/ListMap using companion apply.

I have just added some new commits then. I organized the changes in:

• The original commit, improving the performance of the collections and changing ListSet to provide insertion-order iteration;
• Adding tests for both collections regarding some core operations. I found out that I had some bugs in the changes I did in the first commit and this makes sure no regressions happen now nor in the future;
• Making the two collections similar by renaming and reordering methods, improving their Scaladoc and their code style. Regarding this I removed the Scaladoc of most methods, as the text inherited by the superclasses is in general well written. On the other hand, I improved the class and object-level Scaladoc by making explicit the traversal order guarantee and the time complexity of the operations;
• Adding a SerialVersionUID annotation that was missing in ListSet and including ListSet in the serialization stability test in order to ensure that future changes to this collection do not break the serialization format (or at least alert that a break occurred).

other than these minor comments, looks good!

I have just pushed the modifications you suggested :)

LGTM! thanks for keeping up with the pedantic reviewer :)

/rebuild

No problem at all, they were good suggestions :)