[Issue 14223] New: TimSort algorithm is incorrect
https://issues.dlang.org/show_bug.cgi?id=14223 Issue ID: 14223 Summary: TimSort algorithm is incorrect Product: D Version: future Hardware: All OS: All Status: NEW Severity: normal Priority: P1 Component: Phobos Assignee: nob...@puremagic.com Reporter: acehr...@yahoo.com The following article describes and proposes a fix for a common bug in the TimSort algorithm: http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/ ketmar agrees that Phobos's version of TimSort has the same bug: http://forum.dlang.org/thread/mcigvq$11p0$1...@digitalmars.com#post-mciit8:242dvo:24102:40digitalmars.com Ali --
[Issue 14223] TimSort algorithm is incorrect
https://issues.dlang.org/show_bug.cgi?id=14223
Ketmar Dark ket...@ketmar.no-ip.org changed:
What|Removed |Added
CC||ket...@ketmar.no-ip.org
--- Comment #1 from Ketmar Dark ket...@ketmar.no-ip.org ---
a possible patch:
fixes TimSort implementation, according to
http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/
diff --git a/std/algorithm/sorting.d b/std/algorithm/sorting.d
index a71eb47..f40e957 100644
--- a/std/algorithm/sorting.d
+++ b/std/algorithm/sorting.d
@@ -1230,21 +1230,21 @@ private template TimSortImpl(alias pred, R)
while (stackLen 1)
{
immutable run3 = stackLen - 1;
-immutable run2 = stackLen - 2;
+auto run2 = stackLen - 2;
immutable run1 = stackLen - 3;
-if (stackLen = 3 stack[run1].length = stack[run2].length
+ stack[run3].length)
+immutable run0 = stackLen - 4;
+if ((stackLen = 3 stack[run1].length = stack[run2].length
+ stack[run3].length) ||
+(stackLen = 4 stack[run0].length = stack[run2].length
+ stack[run1].length))
{
-immutable at = stack[run1].length = stack[run3].length
-? run1 : run2;
-mergeAt(range, stack[0 .. stackLen], at, minGallop, temp);
---stackLen;
+if (stack[run1].length stack[run3].length)
+--run2;
}
-else if (stack[run2].length = stack[run3].length)
+else if (stackLen 2 || stack[run2].length
stack[run3].length)
{
-mergeAt(range, stack[0 .. stackLen], run2, minGallop,
temp);
---stackLen;
+break; // invariant is established
}
-else break;
+mergeAt(range, stack[0 .. stackLen], run2, minGallop, temp);
+--stackLen;
}
}
i haven't analyzed the code, though, and didn't run any unittests besides the
simplest ones, so i can't guarantee that i did it right.
so hereby i sommon someone more knowledgeable to properly check it.
--
[Issue 4650] Static data that must be scanned by the GC should be grouped
https://issues.dlang.org/show_bug.cgi?id=4650 --- Comment #9 from Rainer Schuetze r.sagita...@gmx.de --- Actually the patch needs https://github.com/D-Programming-Language/druntime/pull/1180 (and https://github.com/D-Programming-Language/dmd/pull/4445 for Win64) to have any effect. --
[Issue 14220] New: Bad codegen for optimized std.conv.text in combination with concatenation
https://issues.dlang.org/show_bug.cgi?id=14220
Issue ID: 14220
Summary: Bad codegen for optimized std.conv.text in combination
with concatenation
Product: D
Version: D2
Hardware: x86_64
OS: Windows
Status: NEW
Severity: regression
Priority: P1
Component: DMD
Assignee: nob...@puremagic.com
Reporter: r.sagita...@gmx.de
module test;
import std.conv;
void main()
{
string s = err: ~ text(14);
}
Compiling this on win64 with:
dmd -g -m64 -release -inline -O test.d
generates a crashing program. The error seems to disappear if one of -release
,-inline and -O is removed. It also does not happen without the concatenation.
--
[Issue 14220] Bad codegen for optimized std.conv.text in combination with concatenation
https://issues.dlang.org/show_bug.cgi?id=14220 Rainer Schuetze r.sagita...@gmx.de changed: What|Removed |Added Keywords||wrong-code --- Comment #1 from Rainer Schuetze r.sagita...@gmx.de --- According to git-bisect this has been introduced with https://github.com/D-Programming-Language/dmd/pull/4408, so it is not in dmd 2.067 beta2. --
[Issue 14221] New: Investigate the impact of calling destructors during garbage collection
https://issues.dlang.org/show_bug.cgi?id=14221 Issue ID: 14221 Summary: Investigate the impact of calling destructors during garbage collection Product: D Version: D2 Hardware: x86 OS: Mac OS X Status: NEW Severity: normal Priority: P1 Component: DMD Assignee: nob...@puremagic.com Reporter: and...@erdani.com Per http://forum.dlang.org/post/mchtl3$ccp$1...@digitalmars.com, calling the destructor of a struct member inside a class may do things like dereferencing a counter. Currently destructors don't have special provisions for working from multiple threads (e.g. File uses thread-local reference counting). A possible approach is calling each destructor from the same thread that created the object. One possibility is we may deem the lapse benign, i.e. if a refcounted struct has gotten all the way down to being collected, then a mistake in updating the counter may at worst leave it for the next collection cycle. --
[Issue 14222] New: emplace implicit dynamic to static array fails
https://issues.dlang.org/show_bug.cgi?id=14222
Issue ID: 14222
Summary: emplace implicit dynamic to static array fails
Product: D
Version: D2
Hardware: All
OS: All
Status: NEW
Severity: normal
Priority: P1
Component: Phobos
Assignee: nob...@puremagic.com
Reporter: john.loughran.col...@gmail.com
struct S
{
this(int[3] a){}
}
unittest
{
auto s0 = S([1,2,3]); //OK
import std.conv : emplace;
auto s1 = emplace!S(s0, [1,2,3]); //Error
}
std/conv.d(4067): Error: static assert S cannot be emplaced from (int[]).
std/conv.d(4132):instantiated from here: emplaceImpl!(int[])
emplaceTest.d(10):instantiated from here: emplace!(S, int[])
--
[Issue 14221] Investigate the impact of calling destructors during garbage collection
https://issues.dlang.org/show_bug.cgi?id=14221 Nick Treleaven ntrel-...@mybtinternet.com changed: What|Removed |Added CC||ntrel-...@mybtinternet.com --- Comment #1 from Nick Treleaven ntrel-...@mybtinternet.com --- Related: https://issues.dlang.org/show_bug.cgi?id=4624 --
[Issue 14220] Bad codegen for optimized std.conv.text in combination with concatenation
https://issues.dlang.org/show_bug.cgi?id=14220 Ketmar Dark ket...@ketmar.no-ip.org changed: What|Removed |Added CC||ket...@ketmar.no-ip.org --- Comment #2 from Ketmar Dark ket...@ketmar.no-ip.org --- just in case: it's ok with GNU/Linux, x86. so this seems to be 64-bit issue. --
[Issue 14199] [REG2.067a] Dwarf Error: mangled line number section
https://issues.dlang.org/show_bug.cgi?id=14199 github-bugzi...@puremagic.com changed: What|Removed |Added Status|NEW |RESOLVED Resolution|--- |FIXED --
[Issue 14199] [REG2.067a] Dwarf Error: mangled line number section
https://issues.dlang.org/show_bug.cgi?id=14199 --- Comment #3 from github-bugzi...@puremagic.com --- Commits pushed to master at https://github.com/D-Programming-Language/dmd https://github.com/D-Programming-Language/dmd/commit/b79bea953b3daf1b0fcff1db142ca93b56db2abf fix Issue 14199 - [REG2.067a] Dwarf Error: mangled line number section - wrong sized address was used for 32-bit DWARF https://github.com/D-Programming-Language/dmd/commit/c6b1a32d5e00518695044f54b1d3aa076da60589 Merge pull request # from MartinNowak/fix14199 fix Issue 14199 - [REG2.067a] Dwarf Error: mangled line number section --
