Extension bisect unable to find 2 bad extensions

[JacksonKearl]

Ref #111495

I installed two annoying extensions, and clicked "still bad" when either of them were active. Eventually I got into a bad state where the bisect tool determined the problem to be within core.

We should in theory be able to bisect together a list of bad extensions -- I think this would be very helpful in the general "omg my vscode is so slow whats wrongggg" case where there may be several extensions misbehaving.

[jrieken]

We should in theory be able to bisect together a list of bad extensions

Do you know how? Wouldn't this require to disable arbitrary subsets of extensions which means that it will take quite some steps?

[JacksonKearl]

Yeah I've been pondering this... rough sketch of something that is approx O(nBad * lg(nTotal)):

const findBad = <T>(items: T[], containsBad: (subset: T[]) => boolean, nSplits: number, findAll: boolean): T[] => {
  const bad = []
  if (containsBad(items)) {
    if (items.length === 1) {
      bad.push(...items)
    } else {
      const splits = split(items, nSplits);
      for (const split of splits) {
        const found = findBad(split, containsBad, nSplits, findAll)
        bad.push(...found);
        if (!findAll && found.length) break;
      }
    }
  }
  return bad;
}

Num Bad, Arr Len, Num more checks needed for finding all vs one, num checks needed to find all, num checks needed to find one
1, 5, 1.40, 5.81, 4.402
2, 5, 3.28, 7.564, 4.282
3, 5, 4.30, 8.63, 4.322
4, 5, 4.79, 9, 4.201
5, 5, 5, 9, 4
1, 10, 1.89, 7.794, 5.901
2, 10, 5.67, 11.228, 5.557
3, 10, 8.41, 13.858, 5.439
4, 10, 10.20, 15.55, 5.349
5, 10, 11.55, 16.838, 5.28
1, 50, 3, 12.38, 9.384
2, 50, 11.29, 20.138, 8.844
3, 50, 17.83, 26.52, 8.688
4, 50, 23.77, 32.292, 8.518
5, 50, 28.88, 37.36, 8.472
1, 100, 3.63, 14.454, 10.819
2, 100, 13.67, 24.012, 10.339
3, 100, 22.05, 32.218, 10.164
4, 100, 29.82, 39.85, 10.028
5, 100, 36.71, 46.576, 9.861

So in the normal case where only one item is "bad", it takes ~3 more restarts in a 50-100 extension setup (as it needs to check both halves of a split even if it found a bad item in the first half). The delta grows quickly as more items are bad, as the findOne can exit even earlier but the findAll has lots of subarrays to check.

I'm not sure that this is a common enough use case to warrant the more checks, but I think it would be good to at least make sure that the current implementation is always able to produce one faulty extension in the presence of many (as opposed to currently just erroring out and saying its a problem with core), and the end user can run it multiple times if needed.

full code

function shuffleArray(array) {
  for (let i = array.length - 1; i > 0; i--) {
      const j = Math.floor(Math.random() * (i + 1));
      [array[i], array[j]] = [array[j], array[i]];
  }
  return array;
}

const split = (arr: T[], sections: number) => {
  const workingCopy = [...arr];
  const itemsPerSection = arr.length / sections;
  const splits = []
  for (let i = 0; i < sections; i++) {
    const section = []
    for (let j = 0; j < itemsPerSection; j++) {
      if (workingCopy.length) {
        section.push(workingCopy.shift())
      }
    }
    if (section.length) {
      splits.push(section)
    }
  }
  if (workingCopy.length) {
    splits.push(...workingCopy)
  }
  return splits;
}

let containsBadCallCount = 0;
const findBad = (items: T[], containsBad: (subset: T[]) => boolean, nSplits: number, findAll: boolean): T[] => {
  const bad = []
  containsBadCallCount++;
  if (containsBad(items)) {
    if (items.length === 1) {
      bad.push(...items)
    } else {
      const splits = split(items, nSplits);
      for (const split of splits) {
        const found = findBad(split, containsBad, nSplits, findAll)
        bad.push(...found);
        if (!findAll && found.length) break;
      }
    }
  }
  return bad;
}

const testCallCount = (arrLen: number, numBad: number, numSplits: number) => {
  let containsBadAllCallCount = 0;
  let containsBadOneCallCount = 0;
  const numItrs = 1000
  for (let i = 0; i < numItrs; i++) {
    const arr = shuffleArray(Array.from({length: arrLen}).map((_, i) => i < numBad ? true : false))
    containsBadCallCount = 0;
    const all = findBad(arr, arr => arr.some(x => x), numSplits, true)
    if (all.length !== numBad || all.some(x => !x)) { throw Error('all got ', all, all.length, 'expected something else', arrLen, numBad)}
    containsBadAllCallCount += containsBadCallCount;
    containsBadCallCount = 0;
    const one = findBad(arr, arr => arr.some(x => x), numSplits, false)
    containsBadOneCallCount += containsBadCallCount;
    if (one.length !== 1 || one.some(x => !x)) { throw Error('one got ', one, 'expected something else', arrLen, numBad)}
  }
  console.log(`delta, ${numBad}, ${arrLen}, ${containsBadAllCallCount/numItrs - containsBadOneCallCount/numItrs}`)
}

nSplits = 2
// for (const nSplits of [2,3,4]) {
  for (const len of [5,10,50,100]) {
    for (const numBad of [1,2,3,4,5]) {
      testCallCount(len, numBad, nSplits);
    }
  }
// }

[oerpli]

I have a somewhat related suggestion (which is why I add it here as a comment): Fixing a (set of) extensions.

I would expect this to be a pretty common way to use bisect, as many stacks have one standard extension (for language support/essential functionality) and if the problem is not with that extensions, finding the problem is either hard (finding a similar but different workflow where the problem also occurrs) or impossible (if the problem was with some functionality from the extension).

An example: If for example I am writing a LaTeX document and e.g. the preview functionality from Latex-Workshop doesn't work, any configuration where Latex-workshop is not active, is neither good nor bad but irrelevant (as I cannot perform the good/bad test).

I am not entirely sure whether OP used "2 bad extensions" to only refer to the case of "2 extensions, both are bad" or also "2 extensions being bad together" - I think the latter covers somewhat similar ground to what I'm describing.

[JacksonKearl]

@oerpli that's a good point that isn't handled by the above. Finding the minimal subset collectively satisfying a condition is unfortunately a hard problem, and would require more restarts than likely anyone would want to put up with. (I don't know a way it would be less than the number of extensions you have, and it could potentially be many more)

One idea would be a quick pick for bulk-disabling extensions known to be irrelevant, then running an algorithm on whats left. Alternatively marking known-good extensions then running the basic algorithm already implemented or the more advanced one I proposed, but with the known-good ones never disabled.