Run results for: Tree building performance test

Run details:

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_1) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/78.0.3904.97 Safari/537.36

Browser: Chrome 78

Operating system: Mac OS X 10.15.1

Device Platform: Desktop

Date tested: 4 years ago

Test name	Executions per second
While Loop with cached parent_id	21594.0 Ops/sec
While Loop no caching parent_id	22883.9 Ops/sec
Using ForEach() instead of While Loop	21992.3 Ops/sec
While Loop without cache/continue	22697.5 Ops/sec

Script Preparation code:


// Builds a tree from a flat array of objects. Edited from
// stackoverflow.com/questions/18017869 d3indepth.com/layouts
// github.com/inikulin/parse5 github.com/moappi/json2html (node)
function makeLayoutTree(data) {
  const tree = []
  const dict = Object.create(null)

  let i = data.length

  while (i--) {
    dict[data[i].id] = Object.assign(Object.create(null), data[i])
    dict[data[i].id].children = []
  }

  i = data.length

  while (i--) {
    const pid = data[i].parent_id
    if (pid) {
      dict[pid].children[dict[pid].children.length] = dict[data[i].id]
      continue
    }
    tree[tree.length] = dict[data[i].id]
  }

  return tree
}
// Test version caching len, not caching parent_id
function makeLayoutTree_noCache(data) {
  const tree = []
  const dict = Object.create(null)
  
  let i = data.length

  while (i--) {
    dict[data[i].id] = Object.assign(Object.create(null), data[i])
    dict[data[i].id].children = []
  }

  i = data.length

  while (i--) {
    if (data[i].parent_id) {
      dict[data[i].parent_id].children[
        dict[data[i].parent_id].children.length
      ] = dict[data[i].id]
      continue
    }
    tree[tree.length] = dict[data[i].id]
  }

  return tree
}

// Test version caching len, not caching parent_id or using
// continue
function makeLayoutTree_noCache_noContinue(data) {
  const tree = []
  const dict = Object.create(null)
  
  let i = data.length

  while (i--) {
    dict[data[i].id] = Object.assign(Object.create(null), data[i])
    dict[data[i].id].children = []
  }

  i = data.length

  while (i--) {
    if (data[i].parent_id) {
      dict[data[i].parent_id].children[
        dict[data[i].parent_id].children.length
      ] = dict[data[i].id]
    } else {
	  tree[tree.length] = dict[data[i].id]
    }
  }

  return tree
}

// Test version with forEach instead of while loops
function makeLayoutTree_forEach(data) {
  const tree = []
  const dict = Object.create(null)

  data.forEach(o => {
    dict[o.id] = Object.assign(Object.create(null), o, { children: [] })
  })

  data.forEach(o => {
    o.parent_id
      ? dict[o.parent_id].children.push(dict[o.id])
      : tree.push(dict[o.id])
  })

  return tree
}


sample1 = [
  { id: 1, parent_id: 0 },
  { id: 2, parent_id: 1 },
  { id: 3, parent_id: 1 },
  { id: 4, parent_id: 2 },
  { id: 5, parent_id: 0 },
  { id: 6, parent_id: 0 },
  { id: 7, parent_id: 4 },
]

sample2 = [
  {
    id: 1,
    Phone: '(403) 125-2552',
    City: 'Coevorden',
    Name: 'Grady',
  },
  {
    id: 2,
    parent_id: 1,
    Phone: '(979) 486-1932',
    City: 'Chełm',
    Name: 'Scarlet',
  },
  {
    id: 3,
    parent_id: 2,
    Phone: '(225) 125-2552',
    City: 'Nola',
    Name: 'Jill',
  },
  {
    id: 4,
    parent_id: 3,
    Phone: '(221) 486-1932',
    City: 'BR',
    Name: 'John Boy',
  },
  {
    id: 5,
    parent_id: 3,
    Phone: '(337) 186-1932',
    City: 'Lafayette',
    Name: 'Stevie',
  },
  {
    id: 6,
    parent_id: 3,
    Phone: '(337) 386-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 7,
    parent_id: 3,
    Phone: '(337) 432-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 8,
    parent_id: 3,
    Phone: '(337) 486-1932',
    City: 'NISH',
    Name: 'Lena',
  },
]


sample3 = [
  {
    id: 31,
    Phone: '(403) 125-2552',
    City: 'Coevorden',
    Name: 'Grady',
  },
  {
    id: 37,
    parent_id: 32,
    Phone: '(337) 432-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 38,
    parent_id: 32,
    Phone: '(337) 486-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 45,
    parent_id: 42,
    Phone: '(337) 186-1932',
    City: 'Lafayette',
    Name: 'Stevie',
  },
  {
    id: 7,
    parent_id: 3,
    Phone: '(337) 432-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 86,
    parent_id: 82,
    Phone: '(337) 386-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 43,
    parent_id: 41,
    Phone: '(225) 125-2552',
    City: 'Nola',
    Name: 'Jill',
  },
  {
    id: 44,
    parent_id: 42,
    Phone: '(221) 486-1932',
    City: 'BR',
    Name: 'John Boy',
  },
  {
    id: 81,
    Phone: '(403) 125-2552',
    City: 'Coevorden',
    Name: 'Grady',
  },
  {
    id: 67,
    parent_id: 62,
    Phone: '(337) 432-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 47,
    parent_id: 42,
    Phone: '(337) 432-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 23,
    parent_id: 21,
    Phone: '(225) 125-2552',
    City: 'Nola',
    Name: 'Jill',
  },
  {
    id: 4,
    parent_id: 3,
    Phone: '(221) 486-1932',
    City: 'BR',
    Name: 'John Boy',
  },
  {
    id: 82,
    parent_id: 81,
    Phone: '(979) 486-1932',
    City: 'Chełm',
    Name: 'Scarlet',
  },
  {
    id: 74,
    parent_id: 72,
    Phone: '(221) 486-1932',
    City: 'BR',
    Name: 'John Boy',
  },
  {
    id: 62,
    parent_id: 61,
    Phone: '(979) 486-1932',
    City: 'Chełm',
    Name: 'Scarlet',
  },
  {
    id: 83,
    parent_id: 81,
    Phone: '(225) 125-2552',
    City: 'Nola',
    Name: 'Jill',
  },
  {
    id: 27,
    parent_id: 22,
    Phone: '(337) 432-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 55,
    parent_id: 52,
    Phone: '(337) 186-1932',
    City: 'Lafayette',
    Name: 'Stevie',
  },
  {
    id: 1,
    Phone: '(403) 125-2552',
    City: 'Coevorden',
    Name: 'Grady',
  },
  {
    id: 71,
    Phone: '(403) 125-2552',
    City: 'Coevorden',
    Name: 'Grady',
  },
  {
    id: 48,
    parent_id: 42,
    Phone: '(337) 486-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 36,
    parent_id: 32,
    Phone: '(337) 386-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 76,
    parent_id: 72,
    Phone: '(337) 386-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 2,
    parent_id: 1,
    Phone: '(979) 486-1932',
    City: 'Chełm',
    Name: 'Scarlet',
  },
  {
    id: 46,
    parent_id: 42,
    Phone: '(337) 386-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 35,
    parent_id: 32,
    Phone: '(337) 186-1932',
    City: 'Lafayette',
    Name: 'Stevie',
  },
  {
    id: 53,
    parent_id: 51,
    Phone: '(225) 125-2552',
    City: 'Nola',
    Name: 'Jill',
  },
  {
    id: 72,
    parent_id: 71,
    Phone: '(979) 486-1932',
    City: 'Chełm',
    Name: 'Scarlet',
  },
  {
    id: 65,
    parent_id: 62,
    Phone: '(337) 186-1932',
    City: 'Lafayette',
    Name: 'Stevie',
  },
  {
    id: 73,
    parent_id: 71,
    Phone: '(225) 125-2552',
    City: 'Nola',
    Name: 'Jill',
  },
  {
    id: 25,
    parent_id: 22,
    Phone: '(337) 186-1932',
    City: 'Lafayette',
    Name: 'Stevie',
  },
  {
    id: 63,
    parent_id: 61,
    Phone: '(225) 125-2552',
    City: 'Nola',
    Name: 'Jill',
  },
  {
    id: 68,
    parent_id: 62,
    Phone: '(337) 486-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 52,
    parent_id: 51,
    Phone: '(979) 486-1932',
    City: 'Chełm',
    Name: 'Scarlet',
  },
  {
    id: 84,
    parent_id: 82,
    Phone: '(221) 486-1932',
    City: 'BR',
    Name: 'John Boy',
  },
  {
    id: 66,
    parent_id: 62,
    Phone: '(337) 386-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 34,
    parent_id: 32,
    Phone: '(221) 486-1932',
    City: 'BR',
    Name: 'John Boy',
  },
  {
    id: 3,
    parent_id: 2,
    Phone: '(225) 125-2552',
    City: 'Nola',
    Name: 'Jill',
  },
  {
    id: 58,
    parent_id: 52,
    Phone: '(337) 486-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 78,
    parent_id: 72,
    Phone: '(337) 486-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 88,
    parent_id: 82,
    Phone: '(337) 486-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 33,
    parent_id: 31,
    Phone: '(225) 125-2552',
    City: 'Nola',
    Name: 'Jill',
  },
  {
    id: 87,
    parent_id: 82,
    Phone: '(337) 432-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 57,
    parent_id: 52,
    Phone: '(337) 432-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 8,
    parent_id: 3,
    Phone: '(337) 486-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 64,
    parent_id: 62,
    Phone: '(221) 486-1932',
    City: 'BR',
    Name: 'John Boy',
  },
  {
    id: 85,
    parent_id: 82,
    Phone: '(337) 186-1932',
    City: 'Lafayette',
    Name: 'Stevie',
  },
  {
    id: 21,
    Phone: '(403) 125-2552',
    City: 'Coevorden',
    Name: 'Grady',
  },
  {
    id: 61,
    Phone: '(403) 125-2552',
    City: 'Coevorden',
    Name: 'Grady',
  },
  {
    id: 77,
    parent_id: 72,
    Phone: '(337) 432-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 56,
    parent_id: 52,
    Phone: '(337) 386-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 28,
    parent_id: 22,
    Phone: '(337) 486-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 42,
    parent_id: 41,
    Phone: '(979) 486-1932',
    City: 'Chełm',
    Name: 'Scarlet',
  },
  {
    id: 51,
    Phone: '(403) 125-2552',
    City: 'Coevorden',
    Name: 'Grady',
  },
  {
    id: 75,
    parent_id: 72,
    Phone: '(337) 186-1932',
    City: 'Lafayette',
    Name: 'Stevie',
  },
  {
    id: 54,
    parent_id: 52,
    Phone: '(221) 486-1932',
    City: 'BR',
    Name: 'John Boy',
  },
  {
    id: 6,
    parent_id: 3,
    Phone: '(337) 386-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 24,
    parent_id: 22,
    Phone: '(221) 486-1932',
    City: 'BR',
    Name: 'John Boy',
  },
  {
    id: 32,
    parent_id: 31,
    Phone: '(979) 486-1932',
    City: 'Chełm',
    Name: 'Scarlet',
  },
  {
    id: 22,
    parent_id: 21,
    Phone: '(979) 486-1932',
    City: 'Chełm',
    Name: 'Scarlet',
  },
  {
    id: 5,
    parent_id: 3,
    Phone: '(337) 186-1932',
    City: 'Lafayette',
    Name: 'Stevie',
  },
  {
    id: 41,
    Phone: '(403) 125-2552',
    City: 'Coevorden',
    Name: 'Grady',
  },
  {
    id: 26,
    parent_id: 22,
    Phone: '(337) 386-1932',
    City: 'NISH',
    Name: 'Lena',
  },
]

Tests:

While Loop with cached parent_id
makeLayoutTree(sample1) makeLayoutTree(sample2) makeLayoutTree(sample3)
While Loop no caching parent_id
makeLayoutTree_noCache(sample1) makeLayoutTree_noCache(sample2) makeLayoutTree_noCache(sample3)
Using ForEach() instead of While Loop
makeLayoutTree_forEach(sample1) makeLayoutTree_forEach(sample2) makeLayoutTree_forEach(sample3)
While Loop without cache/continue
makeLayoutTree_noCache_noContinue(sample1) makeLayoutTree_noCache_noContinue(sample2) makeLayoutTree_noCache_noContinue(sample3)

Run results for: Tree building performance test

While Loop with cached parent_id

While Loop no caching parent_id

Using ForEach() instead of While Loop

While Loop without cache/continue