sdfmt slow with big nested arrays.

[John-Colvin]

The following takes 2.3s to run through sdfmt even in an ldc release build.

auto longArrayOfArrayOfStrings = [
["hello", "world", "this", "is", "a", "long", "array", "hello", "world", "this", "is", "a", "long", "array"],
["hello", "world", "this", "is", "a", "long", "array", "of", "strings", "with", "multiple", "levels", "of", "depth"],
["hello", "world", "this", "is", "a", "long", "array", "each", "string", "contains", "important", "information", "that", "needs"],
["hello", "world", "this", "is", "a", "long", "array", "to", "be", "stored", "in", "this", "complex", "data", "structure"],
["hello", "world", "this", "is", "a", "long", "array", "the", "array", "of", "arrays", "helps", "to", "organize", "and", "manage"],
["hello", "world", "this", "is", "a", "long", "array", "the", "information", "in", "a", "logical", "and", "efficient", "way"],
["hello", "world", "this", "is", "a", "long", "array", "this", "allows", "for", "easy", "access", "and", "manipulation", "of", "the"],
["hello", "world", "this", "is", "a", "long", "array", "data", "by", "the", "programmer", "who", "has", "a", "good", "understanding"],
["hello", "world", "this", "is", "a", "long", "array", "of", "arrays", "and", "string", "manipulation", "in", "JavaScript"],
["hello", "world", "this", "is", "a", "long", "array", "hello", "world", "this", "is", "a", "long", "array"],
["hello", "world", "this", "is", "a", "long", "array", "of", "strings", "with", "multiple", "levels", "of", "depth"],
["hello", "world", "this", "is", "a", "long", "array", "each", "string", "contains", "important", "information", "that", "needs"],
["hello", "world", "this", "is", "a", "long", "array", "to", "be", "stored", "in", "this", "complex", "data", "structure"],
["hello", "world", "this", "is", "a", "long", "array", "the", "array", "of", "arrays", "helps", "to", "organize", "and", "manage"],
["hello", "world", "this", "is", "a", "long", "array", "the", "information", "in", "a", "logical", "and", "efficient", "way"],
["hello", "world", "this", "is", "a", "long", "array", "this", "allows", "for", "easy", "access", "and", "manipulation", "of", "the"],
["hello", "world", "this", "is", "a", "long", "array", "data", "by", "the", "programmer", "who", "has", "a", "good", "understanding"],
["hello", "world", "this", "is", "a", "long", "array", "of", "arrays", "and", "string", "manipulation", "in", "JavaScript"],
["hello", "world", "this", "is", "a", "long", "array", "hello", "world", "this", "is", "a", "long", "array"],
["hello", "world", "this", "is", "a", "long", "array", "of", "strings", "with", "multiple", "levels", "of", "depth"],
["hello", "world", "this", "is", "a", "long", "array", "each", "string", "contains", "important", "information", "that", "needs"],
["hello", "world", "this", "is", "a", "long", "array", "to", "be", "stored", "in", "this", "complex", "data", "structure"],
["hello", "world", "this", "is", "a", "long", "array", "the", "array", "of", "arrays", "helps", "to", "organize", "and", "manage"],
["hello", "world", "this", "is", "a", "long", "array", "the", "information", "in", "a", "logical", "and", "efficient", "way"],
["hello", "world", "this", "is", "a", "long", "array", "this", "allows", "for", "easy", "access", "and", "manipulation", "of", "the"],
["hello", "world", "this", "is", "a", "long", "array", "data", "by", "the", "programmer", "who", "has", "a", "good", "understanding"],
["hello", "world", "this", "is", "a", "long", "array", "of", "arrays", "and", "string", "manipulation", "in", "JavaScript"],
["hello", "world", "this", "is", "a", "long", "array", "hello", "world", "this", "is", "a", "long", "array"],
["hello", "world", "this", "is", "a", "long", "array", "of", "strings", "with", "multiple", "levels", "of", "depth"],
["hello", "world", "this", "is", "a", "long", "array", "each", "string", "contains", "important", "information", "that", "needs"],
["hello", "world", "this", "is", "a", "long", "array", "to", "be", "stored", "in", "this", "complex", "data", "structure"],
["hello", "world", "this", "is", "a", "long", "array", "the", "array", "of", "arrays", "helps", "to", "organize", "and", "manage"],
["hello", "world", "this", "is", "a", "long", "array", "the", "information", "in", "a", "logical", "and", "efficient", "way"],
["hello", "world", "this", "is", "a", "long", "array", "this", "allows", "for", "easy", "access", "and", "manipulation", "of", "the"],
["hello", "world", "this", "is", "a", "long", "array", "data", "by", "the", "programmer", "who", "has", "a", "good", "understanding"],
["hello", "world", "this", "is", "a", "long", "array", "of", "arrays", "and", "string", "manipulation", "in", "JavaScript"],
["hello", "world", "this", "is", "a", "long", "array", "hello", "world", "this", "is", "a", "long", "array"],
["hello", "world", "this", "is", "a", "long", "array", "of", "strings", "with", "multiple", "levels", "of", "depth"],
["hello", "world", "this", "is", "a", "long", "array", "each", "string", "contains", "important", "information", "that", "needs"],
["hello", "world", "this", "is", "a", "long", "array", "to", "be", "stored", "in", "this", "complex", "data", "structure"],
["hello", "world", "this", "is", "a", "long", "array", "the", "array", "of", "arrays", "helps", "to", "organize", "and", "manage"],
["hello", "world", "this", "is", "a", "long", "array", "the", "information", "in", "a", "logical", "and", "efficient", "way"],
["hello", "world", "this", "is", "a", "long", "array", "this", "allows", "for", "easy", "access", "and", "manipulation", "of", "the"],
["hello", "world", "this", "is", "a", "long", "array", "data", "by", "the", "programmer", "who", "has", "a", "good", "understanding"],
["hello", "world", "this", "is", "a", "long", "array", "of", "arrays", "and", "string", "manipulation", "in", "JavaScript"],
["hello", "world", "this", "is", "a", "long", "array", "hello", "world", "this", "is", "a", "long", "array"],
["hello", "world", "this", "is", "a", "long", "array", "of", "strings", "with", "multiple", "levels", "of", "depth"],
["hello", "world", "this", "is", "a", "long", "array", "each", "string", "contains", "important", "information", "that", "needs"],
["hello", "world", "this", "is", "a", "long", "array", "to", "be", "stored", "in", "this", "complex", "data", "structure"],
["hello", "world", "this", "is", "a", "long", "array", "the", "array", "of", "arrays", "helps", "to", "organize", "and", "manage"],
["hello", "world", "this", "is", "a", "long", "array", "the", "information", "in", "a", "logical", "and", "efficient", "way"],
["hello", "world", "this", "is", "a", "long", "array", "this", "allows", "for", "easy", "access", "and", "manipulation", "of", "the"],
["hello", "world", "this", "is", "a", "long", "array", "data", "by", "the", "programmer", "who", "has", "a", "good", "understanding"],
["hello", "world", "this", "is", "a", "long", "array", "of", "arrays", "and", "string", "manipulation", "in", "JavaScript"],
];

[maxhaton]

Profile

Functions	Modules	CYCLES_NOT_IN_HALT	RETIRED_INST	IPC	RETIRED_BRANCH_INSTRUCTION_MISPREDICTED_PTI	%RETIRED_BRANCH_INSTRUCTION_MISPREDICTED	DATA_CACHE_ACCESSES_PTI	MAB_ALLOC_PTI	%DATA_CACHE_MISS	MISALIGN_LOADS_PTI
const format.span.Span.Split format.span.ListSpan.computeSplit(ref const(format.writer.SolveState), ulong)	sdfmt	8078	23713	2.94	0.81	0.3	298.28	3.11	1.04	0.16
pure nothrow @nogc scope @trusted ulong core.internal.gc.bits.GCBits.setLocked(ulong)	sdfmt	6221	988	0.16	1.32	0.51	446.36	8.4	1.88
void format.writer.SolveState.computeUsedSpans(format.chunk.Chunk[])	sdfmt	3501	10088	2.88	0.96	0.37	316.42	3.16	1	0.12
const format.span.Span.Split format.span.Span.computeSplit(ref const(format.writer.SolveState), ulong)	sdfmt	2276	6439	2.83	0.93	0.34	330.64	3.45	1.04	0.14
const ulong format.span.ListSpan.computeState(ref const(format.writer.SolveState))	sdfmt	1896	5492	2.9	1.13	0.45	291.51	4.62	1.59	0.22
const uint format.span.Span.computeIndent(ref const(format.writer.SolveState), ulong)	sdfmt	1037	2899	2.8	0.97	0.43	337.36	6.35	1.88	0.03
void format.writer.SolveState.computeCost(format.chunk.Chunk[], format.writer.Writer*)	sdfmt	1002	2370	2.37	1.22	0.53	367.51	4.94	1.34	0.17
nothrow void* core.internal.gc.impl.conservative.gc.Gcx.smallAlloc(ulong, ref ulong, uint, const(TypeInfo))	sdfmt	898	2443	2.72	1.27	0.53	318.46	4.79	1.5	0.16
const uint format.writer.SolveState.newLineCount(const(format.chunk.Chunk[]), ulong)	sdfmt	880	2252	2.56	1.38	0.63	396.09	4.44	1.12
DThn16_4core8internal2gc4impl12conservativeQw14ConservativeGC6qallocMFNbmkMxC8TypeInfoZSQDd6memory8BlkInfo	sdfmt	679	1928	2.84	1.04	0.42	314.32	5.19	1.65	0.1
ulong format.span.getAlignIndex(const(format.span.Span), ref const(format.writer.SolveState), ulong)	sdfmt	659	1745	2.65	1.03	0.46	357.02	5.04	1.41	0.06
const ulong format.span.ListSpan.computeAlignIndex(ref const(format.writer.SolveState), ulong)	sdfmt	638	1540	2.41	0.71	0.32	380.52	4.94	1.3
nothrow @nogc scope void core.internal.gc.impl.conservative.gc.Gcx.mark!(false, true, true).mark(core.internal.gc.impl.conservative.gc.Gcx.ScanRange!(false).ScanRange)	sdfmt	597	157	0.26	0.64	0.28	522.29	9.55	1.83
const format.writer.LinePrefix format.writer.SolveState.getLinePrefix(format.chunk.Chunk[], ulong)	sdfmt	571	1396	2.44	0.36	0.16	392.55	5.44	1.39
bool std.container.rbtree.RedBlackTree!(format.span.Span, "a < b", false).RedBlackTree._add(scope format.span.Span)	sdfmt	539	1381	2.56	1.16	0.51	365.68	4.71	1.29

[deadalnix]

pure nothrow @nogc scope @trusted ulong core.internal.gc.bits.GCBits.setLocked(ulong)

Sadness.

[deadalnix]

So, this has been on my radar for a while, but the right solution is to special case lists in the renderer in the same way blocks are.

Also, the GC locking seems to be absurdly expensive, especially for something that is single threaded. Something is not normal in there.