[Issue 7157] Optimiser is O(n^2) w.r.t. function length

[d-bugmail--- via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7157

Basile-z  changed:

   What|Removed |Added

 CC||hoganme...@gmail.com

--- Comment #14 from Basile-z  ---
*** Issue 6401 has been marked as a duplicate of this issue. ***

--

[Issue 7157] Optimiser is O(n^2) w.r.t. function length

[d-bugmail--- via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7157

Iain Buclaw  changed:

   What|Removed |Added

   Priority|P2  |P3

--

[Issue 7157] Optimiser is O(n^2) w.r.t. function length

[d-bugmail--- via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7157

Walter Bright  changed:

   What|Removed |Added

   See Also||https://issues.dlang.org/sh
   ||ow_bug.cgi?id=21121

--

[Issue 7157] Optimiser is O(n^2) w.r.t. function length

[d-bugmail--- via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7157

Walter Bright  changed:

   What|Removed |Added

   See Also||https://issues.dlang.org/sh
   ||ow_bug.cgi?id=6401

--

[Issue 7157] Optimiser is O(n^2) w.r.t. function length

[d-bugmail--- via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7157

Iain Buclaw  changed:

   What|Removed |Added

   Keywords||backend
 CC||ibuc...@gdcproject.org

--

[Issue 7157] Optimiser is O(n^2) w.r.t. function length

[d-bugmail--- via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7157

Steven Schveighoffer  changed:

   What|Removed |Added

 Blocks||21121


Referenced Issues:

https://issues.dlang.org/show_bug.cgi?id=21121
[Issue 21121] Optimizer slowdowns
--

[Issue 7157] Optimiser is O(n^2) w.r.t. function length

[d-bugmail--- via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7157

safety0ff.bugz  changed:

   What|Removed |Added

   See Also|https://issues.dlang.org/sh |
   |ow_bug.cgi?id=19550 |

--

[Issue 7157] Optimiser is O(n^2) w.r.t. function length

[d-bugmail--- via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7157

safety0ff.bugz  changed:

   What|Removed |Added

   See Also||https://issues.dlang.org/sh
   ||ow_bug.cgi?id=19550

--

[Issue 7157] Optimiser is O(n^2) w.r.t. function length

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7157

ZombineDev  changed:

   What|Removed |Added

 CC||petar.p.ki...@gmail.com

--

[Issue 7157] Optimiser is O(n^2) w.r.t. function length

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7157

--- Comment #13 from Walter Bright  ---
Partial fix: https://github.com/dlang/dmd/pull/6356

--

[Issue 7157] Optimiser is O(n^2) w.r.t. function length

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7157

Walter Bright  changed:

   What|Removed |Added

 CC||bugzi...@digitalmars.com

--- Comment #12 from Walter Bright  ---
There is some quadratic behavior in the function bodies of `updaterd` and
`accumaecpx` (look for the loops). They can both be fixed.

--

[Issue 7157] Optimiser is O(n^2) w.r.t. function length

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7157

Jack Stouffer  changed:

   What|Removed |Added

   Keywords||performance
 CC||j...@jackstouffer.com
   Hardware|x86 |All
 OS|Mac OS X|All

--

[Issue 7157] Optimiser is O(n^2) w.r.t. function length

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7157

Andrei Alexandrescu  changed:

   What|Removed |Added

 CC||and...@erdani.com

--- Comment #11 from Andrei Alexandrescu  ---
I just realized that a precise GC using introspection would use exactly this
facility.

--

[Issue 7157] Optimiser is O(n^2) w.r.t. function length

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7157

Daniel Kozak  changed:

   What|Removed |Added

 CC||chalu...@gmail.com

--- Comment #10 from Daniel Kozak  ---
*** Issue 14939 has been marked as a duplicate of this issue. ***

--

[Issue 7157] Optimiser is O(n^2) w.r.t. function length

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7157

--- Comment #9 from Martin Nowak  ---
Could we fix this for now by letting dmd backoff from very big functions?
Or if someone understands accumaecpx well enough, maybe the optimization can be
windowed to 1000 expressions/statements or so.

--

[Issue 7157] Optimiser is O(n^2) w.r.t. function length

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7157

--- Comment #8 from Martin Nowak  ---
Another case of this.
https://github.com/etcimon/botan/issues/8
It took dmd almost 13 minutes to compile botan w/ release optimizations on
heroku (and about 4 minutes on my local machine).

--

[Issue 7157] Optimiser is O(n^2) w.r.t. function length

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7157

--- Comment #7 from Martin Nowak c...@dawg.eu ---
(In reply to Jonathan M Davis from comment #6)
 Which trick are you referring to?

https://github.com/D-Programming-Language/phobos/pull/2767

--

[Issue 7157] Optimiser is O(n^2) w.r.t. function length

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7157

Martin Nowak c...@dawg.eu changed:

   What|Removed |Added

 CC||c...@dawg.eu

--- Comment #4 from Martin Nowak c...@dawg.eu ---
I'm getting excessive compile times for a few phobos modules in release
unittests.
Most notably std.regex.internal.tests, and std.datetime.
Can we try to do the static foreach delegate trick again?

time ../dmd/src/dmd -conf= -I../druntime/import  -w -dip25 -m64  -O -release
-unittest -c -ofgenerated/osx/release/64/unittest/std/datetime.o
-deps=generated/osx/release/64/unittest/std/datetime.deps.tmp std/datetime.d
  180.96 real   132.19 user48.76 sys
time ../dmd/src/dmd -conf= -I../druntime/import  -w -dip25 -m64  -O -release
-unittest -c -ofgenerated/osx/release/64/unittest/std/random.o
-deps=generated/osx/release/64/unittest/std/random.deps.tmp std/random.d
   21.23 real15.68 user 5.53 sys
time ../dmd/src/dmd -conf= -I../druntime/import  -w -dip25 -m64  -O -release
-unittest -c -ofgenerated/osx/release/64/unittest/std/regex/internal/tests.o
-deps=generated/osx/release/64/unittest/std/regex/internal/tests.deps.tmp
std/regex/internal/tests.d
  250.31 real   184.75 user65.55 sys

--

[Issue 7157] Optimiser is O(n^2) w.r.t. function length

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7157

Jonathan M Davis issues.dl...@jmdavisprog.com changed:

   What|Removed |Added

 CC||issues.dl...@jmdavisprog.co
   ||m

--- Comment #6 from Jonathan M Davis issues.dl...@jmdavisprog.com ---
(In reply to Martin Nowak from comment #4)
 Can we try to do the static foreach delegate trick again?

Which trick are you referring to?

--

[Issue 7157] Optimiser is O(n^2) w.r.t. function length

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7157

--- Comment #5 from Martin Nowak c...@dawg.eu ---
Most CPU time is spent in `updaterd` and `accumaecpx` if that helps.

https://github.com/D-Programming-Language/dmd/blob/82b031c22f18334a7edeff437260b6802070a9e3/src/backend/gloop.c#L1263
https://github.com/D-Programming-Language/dmd/blob/e43136308f7eb035d046a99a46ffbdaf880413b7/src/backend/gflow.c#L907

--

[Issue 7157] Optimiser is O(n^2) w.r.t. function length

[d-bugmail]

https://d.puremagic.com/issues/show_bug.cgi?id=7157


Artem Tarasov lomerei...@gmail.com changed:

   What|Removed |Added

 CC||bearophile_h...@eml.cc


--- Comment #3 from Artem Tarasov lomerei...@gmail.com 2014-01-02 12:23:30 
PST ---
*** Issue 11859 has been marked as a duplicate of this issue. ***

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---

[Issue 7157] Optimiser is O(n^2) w.r.t. function length

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=7157



--- Comment #2 from Don clugd...@yahoo.com.au 2011-12-23 00:14:59 PST ---
See bug 2396. I'd close this as a duplicate, except that the test case in this
one is much better.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---

[Issue 7157] Optimiser is O(n^2) w.r.t. function length

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=7157


Don clugd...@yahoo.com.au changed:

   What|Removed |Added

 CC||clugd...@yahoo.com.au


--- Comment #1 from Don clugd...@yahoo.com.au 2011-12-22 21:02:59 PST ---
This is most likely the O(n^^2) behaviour of the optimization of the comma
operator, where n is the maximum depth of comma expressions.
Each pass through the optimizer only removes the deepest comma, and each pass
involves several operations which are O(n). Even finding the deepest comma is
O(n).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---