InflectionList.addItems really slow

[KarolS]

This loop: https://github.com/alpheios-project/alpheios-core/blob/master/packages/inflection-tables/lib/inflection-list.js#L36

has quadratic complexity, which makes the whole extension really slow. It can take several seconds for the definition to pop up.

Here is a partial flame graph:

Here is my suggestion how to fix it:

constructor (type) {
    this.type = type
    this.items = [] // Suffixes or forms
    this.itemIds= new Set() // Ids of suffixes or forms
    this.footnotesMap = new Map() // Footnotes (if any)
  }

  addItem (item) {
    if (!item) {
      throw new Error('Inflection item cannot be empty')
    }
    this.itemIds.add(item.id)
    this.items.push(item)
  }

  /**
   * Adds suffix of form items
   * @param {Suffix[] | Form[] | Paradigm[]} items
   */
  addItems (items) {
    if (!items) {
      throw new Error('Inflection items cannot be empty')
    }
    if (!Array.isArray(items)) {
      throw new Error('Inflection items must be in an array')
    }
    if (items.length === 0) {
      throw new Error('Inflection items array must not be empty')
    }
    // Store only new items, avoid duplicates
    for (const item of items) {
      if (!this.itemIds.has(item.id)) {
        this.itemIds.add(item.id)
        this.items.push(item)
      }
    }
  }

[irina060981]

Hello, @KarolS

I could see that you suggest to use addItem instead of addItems. But the way it is added the same. So your suggestion to remove duplicate check?

[KarolS]

I'm not suggesting to use addItem, I just changed it so that it maintains the itemIds invariant. I don't know if it is used anywhere at all. If addItems is optimized, then it can still be used just fine.

The main reason this.addItems is slow is that this.hasItem is slow, so I replaced it with much faster this.itemIds.has.

[irina060981]

oh, I see - thank you - will review it

[irina060981]

Fixed

[KarolS]

I'm sorry I'm saying this so late, but I only just checked.

The new implementation is still using a list and will still have quadratic performance. Why wasn't a set used?

https://github.com/alpheios-project/alpheios-core/commit/c4502de1ed96737e7fb1a18c0fc55d70366ce43d#diff-7ae71f5289ebf8f3182a3fa7366481c55a25bedeb820b939ac4415536bb9765bR8

[irina060981]

Such a change will need bigger refactoring of this library. For now this project is almost freezed - hoping for better situation in future.

[KarolS]

The only set that would be required to make it non-quadratic is itemIds, it would be a small and completely local change. What do you mean by "freezed"?

[irina060981]

The only set that would be required to make it non-quadratic is itemIds, it would be a small and completely local change. This repo has a lot of references, so any change would need much testing If you need it in your project - you could download it locally and do changes you need.

What do you mean by "freezed"? The project has only small suport - no changes, no upgrade.