Investigation of possible reprentations of concatenated strings

[ruben-ayrapetyan]

Hello.

Pull request #635 removed special representation of concatenated strings.

While the change reduced memory usage and significantly improved performance for many cases, it also significantly increased memory consumption for other cases. For example:

var i = '0123456789ABCDEF';

for (j = 0; j < 12; j++)
{
  i += i;
}

print (i[124]);

Please, see memory statistics for the following versions:
6697523 (base version) -> 3b0f61a (the patch)

• Heap stats:
  • Peak allocated chunks count = 1037 -> 3081
  • Peak allocated = 66292 -> 197108 bytes
  • Peak waste = 199 -> 199 bytes
• Pools stats:
  • Peak pools: 8 -> 2052
  • Peak allocated chunks: 63 -> 16416

var i = '0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF';
var j = 'abcdefghijklmnopabcdefghijklmnopabcdefghijklmnopabcdefghijklmnop';

var a = '';

for (k = 0; k < 16; k++)
{
  if (k % 4 == 0)
  {
    a += (i + j);
  }
  else if (k % 2 == 0)
  {
    i += a;
  }
  else
  {
    j += a;
  }
}

print (a[124]);

• Heap stats:
  • Peak allocated chunks count = 367 -> 2533
  • Peak allocated = 23420 -> 162044 bytes
  • Peak waste = 191 -> 191 bytes
• Pools stats:
  • Peak pools: 10 -> 1943
  • Peak allocated chunks: 73 -> 15540

var i = '01';
var j = 'ab';

var a = '';

for (k = 0; k < 16; k++)
{
  if (k % 4 == 0)
  {
    a += (i + j);
  }
  else if (k % 2 == 0)
  {
    i += a;
  }
  else
  {
    j += a;
  }
}

print (a[124]);

• Heap stats:
  • Peak allocated chunks count = 63 -> 92
  • Peak allocated = 3843 -> 5766 bytes
  • Peak waste = 191 -> 191 bytes
• Pools stats:
  • Peak pools: 10 -> 56
  • Peak allocated chunks: 75 -> 525

Please, see also the related conversation: https://github.com//pull/635#issuecomment-143723345

[LaszloLango]

I made some experiments with the string concatenation. First I checked the stack sizes on some testcases. On string-base64.js (sunspider) the old string concatenation version had a really huge stack (+300K). On the current master we can run this test too with much better memory usage and performance. On the mentioned custom test cases the stack sizes are not so horrible. The simplest solution had the best results for me. I made a mixed version that use both the old concatenation mechanism and the new. I made a custom benchmark for testing (uploaded to my fork). My results were the following on x86:
base rev: 3b0f61a

Benchmark	RSS (+ is better)	Perf (+ is better)
string-base64.js	192-> 192 (0.000)	44.5034->44.4398 (0.143)
string_concat_lit_1.js	228-> 68 (70.175)	0.7718->1.0314 (-33.636)
string_concat_lit_2.js	192-> 60 (68.750)	0.5432->0.8284 (-52.504)
string_concat_lit_3.js	48-> 48 (0.000)	0.0172->0.0132 (23.256)
string_concat_lit_4.js	52-> 52 (0.000)	0.0168->0.0156 (7.143)
string_concat_lit_5.js	48-> 48 (0.000)	0.013-> 0.02 (-53.846)
string_concat_lit_6.js	72-> 76 (-5.556)	0.8192->0.8058 (1.636)
string_concat_lit_7.js	36-> 44 (-22.222)	0.0274-> 0.027 (1.460)
string-fasta-1.0.2.js	64-> 68 (-6.250)	1.4442->2.9036 (-101.052)
Geometric mean:	RSS reduction: 20.4373%	Speed up: -17.739%

I think the biggest problem with the old concat mechanism is that build a tree and use recursive algorithm to handle that. One possible further investigation could be to change the recursive pre-order traversal to iterative pre-order traversal.
Benchmark: https://github.com/LaszloLango/jerryscript/tree/string_concat_benchmark
Mixed concat solution: https://github.com/LaszloLango/jerryscript/tree/string_dev_5

[zherczeg]

This is invalid now.