Run results for: Tree building performance test w/ larger array (single invocation) v4

Run details:

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:71.0) Gecko/20100101 Firefox/71.0

Browser: Firefox 71

Operating system: Mac OS X 10.15

Device Platform: Desktop

Date tested: 4 years ago

Test name	Executions per second
While Loop with cached parent_id	47353.9 Ops/sec
While Loop no caching parent_id	43586.6 Ops/sec
Using ForEach() instead of While Loop	41848.3 Ops/sec
While Loop without cache, using if/else instead of continue	50547.1 Ops/sec
While Loop without cache, using spread with assign	26750.3 Ops/sec
While Loop without cache, using spread only	62886.8 Ops/sec
For Loop version	52101.7 Ops/sec
Using ForEach() instead of While Loop, spread only	60124.4 Ops/sec
Using ForEach() instead of While Loop, spread only, no push()	60508.8 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 = {}

  let i = data.length

  while (i--) {
    dict[data[i].id] = Object.assign({}, 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 not caching parent_id
function makeLayoutTree_noCache(data) {
  const tree = []
  const dict = {}
  
  let i = data.length

  while (i--) {
    dict[data[i].id] = Object.assign({}, 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 not caching parent_id, Object.assign with
// 2 objects
function makeLayoutTree_noCache(data) {
  const tree = []
  const dict = {}
  
  let i = data.length

  while (i--) {
    dict[data[i].id] = Object.assign({}, data[i], { 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 not caching parent_id, Object.assign with spread
// operator
function makeLayoutTree_noCache_assignSpread(data) {
  const tree = []
  const dict = {}
  
  let i = data.length

  while (i--) {
    dict[data[i].id] = Object.assign({}, { ...data[i], 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 not caching parent_id, with direct spread
// operator only, no Object.create(null)
function makeLayoutTree_noCache_spread(data) {
  const tree = []
  const dict = {}
  
  let i = data.length

  while (i--) {
    dict[data[i].id] = { ...data[i], 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 not caching parent_id, using if/else instead
// continue
function makeLayoutTree_noCache_noContinue(data) {
  const tree = []
  const dict = {}
  
  let i = data.length

  while (i--) {
    dict[data[i].id] = Object.assign({}, 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 = {}

  data.forEach(o => {
    dict[o.id] = Object.assign({}, o, { children: [] })
  })

  data.forEach(o => {
    o.parent_id
      ? dict[o.parent_id].children.push(dict[o.id])
      : tree.push(dict[o.id])
  })

  return tree
}

// Test version with forEach instead of while loops, no object.assign
function makeLayoutTree_forEach2(data) {
  const tree = []
  const dict = {}

  data.forEach(o => {
    dict[o.id] = { ...o, children: [] }
  })

  data.forEach(o => {
    o.parent_id
      ? dict[o.parent_id].children.push(dict[o.id])
      : tree.push(dict[o.id])
  })

  return tree
}

// Test version with forEach instead of while loops, no object.assign
function makeLayoutTree_forEach3(data) {
  const tree = []
  const dict = {}

  data.forEach(o => {
    dict[o.id] = { ...o, children: [] }
  })

  data.forEach(o => {
    o.parent_id
      ? dict[o.parent_id].children[dict[o.parent_id].children.length] = dict[o.id]
      : tree[tree.length] = dict[o.id]
  })

  return tree
}

// With For Loop instead of While Loop
function makeLayoutTree_forLoop(data) {
  const tree = []
  const dict = {}

  for (let i = 0; i < data.length; i++) {
    dict[data[i].id] = Object.assign({}, data[i])
    dict[data[i].id].children = []
  }

  for (let j = 0; j < data.length; j++) {
    if (data[j].parent_id) {
      dict[data[j].parent_id].children[
        dict[data[j].parent_id].children.length
      ] = dict[data[j].id]
      continue
    }
    tree[tree.length] = dict[data[j].id]
  }

  return tree
}


sample1 = [
  {
    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)
While Loop no caching parent_id
makeLayoutTree_noCache(sample1)
Using ForEach() instead of While Loop
makeLayoutTree_forEach(sample1)
While Loop without cache, using if/else instead of continue
makeLayoutTree_noCache_noContinue(sample1)
While Loop without cache, using spread with assign
makeLayoutTree_noCache_assignSpread(sample1)
While Loop without cache, using spread only
makeLayoutTree_noCache_spread(sample1)
For Loop version
makeLayoutTree_forLoop(sample1)
Using ForEach() instead of While Loop, spread only
makeLayoutTree_forEach2(sample1)
Using ForEach() instead of While Loop, spread only, no push()
makeLayoutTree_forEach3(sample1)

Run results for: Tree building performance test w/ larger array (single invocation) v4

While Loop with cached parent_id

While Loop no caching parent_id

Using ForEach() instead of While Loop

While Loop without cache, using if/else instead of continue

While Loop without cache, using spread with assign

While Loop without cache, using spread only

For Loop version

Using ForEach() instead of While Loop, spread only

Using ForEach() instead of While Loop, spread only, no push()