NotificationsYou must be signed in to change notification settings
Fork3.1k
Star14.4k

Fix pathologically slow compilation of some pattern matches since 2.13.7#10258

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Jump to bottom

Merged

dwijnand merged 1 commit intoscala:2.13.xfromKisaragiEffective:t12499

Mar 2, 2023

Merged

Fix pathologically slow compilation of some pattern matches since 2.13.7#10258

dwijnand merged 1 commit intoscala:2.13.xfromKisaragiEffective:t12499

Mar 2, 2023

Conversation

Copy link

Contributor

KisaragiEffective commentedJan 7, 2023•
edited by SethTisue
Loading

by switching the pattern matcher to usemutable.LinkedHashSet instead ofListSet

fixesscala/bug#12499

scala-jenkins added this to the2.13.11 milestone

Jan 7, 2023

Copy link

Member

lrytz commentedJan 9, 2023

This seems to non-deterministically failpartest test/files/neg/t7020.scala. I assume it's about the undefined Set iteration order.

Copy link

ContributorAuthor

KisaragiEffective commentedJan 9, 2023

I feel the same, passed/failed on local randomly. Which should I do to fix it?

modify patmat's logic to fix t7020 -- This would make large diff and takes longer time.
update t7020 errors and leave patmat's logic as is -- I don't think it will resolve the issue.
usejava.util.LinkedHashSet and leave t7020 as is --LinkedHashSet is not immutable since it's from Java. Would it cause an issue?
backport part of Add SeqSet and SetFromMap implementations scala-library-next#35 to use, and leave t7020 as is

michelou mentioned this pull request

Jan 14, 2023

fix: Revert "chore: update Scala 2 version"flix/flix#4916

Merged

lrytz requested a review fromdwijnand

January 16, 2023 09:31

Copy link

Member

dwijnand commentedJan 19, 2023

@KisaragiEffective I don't mind if we switch to java.util.LinkedHashSet.

Copy link

ContributorAuthor

KisaragiEffective commentedJan 22, 2023

I'm not sure why it was failed...

lrytz reviewed

Jan 25, 2023

View reviewed changes

src/compiler/scala/tools/nsc/transform/patmat/Logic.scala Outdated

		defcreate(ps:Iterable[Prop])= psmatch {
		caseps:Set[Prop]=>newAnd(ps)
		case _=>newAnd(ps.to(scala.collection.immutable.ListSet))
		case _=>newAnd(new java.util.LinkedHashSet[Prop](ps.toSet.asJava).asScala.to(Set))

Copy link

Member

Choose a reason for hiding this comment

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

ps.toSet creates an immutable HashSet which has non-deterministic iteration order.

I think we can use Scala'smutable.LinkedHashSet instead of Java's. Maybe the best option is to change theAnd andOr case classes to have amutable.LinkedHashSet[Prop] parameter? That would express the fact that an ordered collection is required.

Otherwise, usecollection.Set[Prop]?

@dwijnand what do you think?

Copy link

Member

dwijnandJan 25, 2023

Choose a reason for hiding this comment

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

Isn'tjava.util.LinkedHashSet known to be faster thanmutable.LinkedHashSet? Good catch on the toSet: we need to build up the set in insertion-order of the iterable.

I don't mind if we change the parameter either.

Copy link

Member

lrytzJan 25, 2023

Choose a reason for hiding this comment

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

The Java version is possibly still faster, but our LinkedHashSet was recently brought up to date (#10221). Compared to ListSet which we are replacing here, it's likely going to be fine.

Copy link

Member

SethTisue commentedFeb 17, 2023

@KisaragiEffective interested in returning to this...?

Copy link

ContributorAuthor

KisaragiEffective commentedFeb 18, 2023

It's still failed on t7020. Are there other implicit assumptions?

Copy link

Member

lrytz commentedFeb 20, 2023

The current version still callstoSet, which creates an immutable HashSet. See my comment here:#10258 (comment)

lrytz assigneddwijnand

Feb 20, 2023

KisaragiEffective marked this pull request as ready for review

February 21, 2023 06:44

Copy link

ContributorAuthor

KisaragiEffective commentedFeb 21, 2023

they're green exceptcombined step 🎉

Patmat: Switch from ListSet to mutable.LinkedHashSet

5d5d00f

* experiment fix for SI-12499 (patmat perf)* use java.util.LinkedHashSet* switch j.u to s.c.m LinkedHashSet* avoid convert to Set to keep deterministic iteration order* fix compile errorCo-authored-by: Dale Wijnand <dale.wijnand@gmail.com>

dwijnand force-pushed thet12499 branch fromc226f8b to5d5d00fCompare

March 2, 2023 10:09

KisaragiEffective changed the title~~experiment fix for SI-12499 (patmat perf)~~Patmat: Switch from ListSet to mutable.LinkedHashSet (SI-12499)

Mar 2, 2023

Copy link

ContributorAuthor

KisaragiEffective commentedMar 2, 2023

(changed title according to squashed commit)

dwijnand approved these changes

Mar 2, 2023

View reviewed changes

dwijnand merged commit5ecdcf8 intoscala:2.13.x

Mar 2, 2023

SethTisue changed the title~~Patmat: Switch from ListSet to mutable.LinkedHashSet (SI-12499)~~Fix pathologically slow compilation of some pattern matches since 2.13.7

Mar 2, 2023

Copy link

michelou commentedMar 6, 2023

@SethTisue IMO the issue is only partially fixed; seemy comment inflix/flix PR 4916.

Copy link

Member

SethTisue commentedMar 6, 2023

@michelou ah, sorry to hear that. I wonder if what you're experiencing now has some entirely different cause, or if it's more that the PR we have needs a followup adjustment.