[Bug]: `DynamicTable.add_row` is quadratic in the number of rows

[h-mayorquin]

What happened?

Writing a 21,330-row EventsTable took 124 s, of which about 123.5 s was is_ragged. I found it writing that table from neuroconv, where the source is a complete twelve-minute pyPhotometry recording, a 364 KB file whose digital line pulses at 30 Hz. Real sessions run for hours, so this gets worse quickly.

catalystneuro/neuroconv#1920

The reason is a (most likely unintended) check on is_ragged.

add_row re-derives from the whole table, on every insert, a fact that only the element just appended can change. It calls is_ragged on the entire column after appending a single value, and every caller pays it as check_ragged defaults to True:
https://github.com/hdmf-dev/hdmf/blob/6.1.0/src/hdmf/common/table.py#L847-L852

enforce_unique_id has the same shape, though it defaults to False and so is only paid by callers who ask for it: row_id in self.id iterates the whole ElementIdentifiers column as it defines no __contains__:
https://github.com/hdmf-dev/hdmf/blob/6.1.0/src/hdmf/common/table.py#L835-L837

So each check costs O(n) at row n and the script below fills a one column table in O(n^2). Note that its fill leaves both off unless asked, where hdmf's own default has check_ragged=True:

  rows  check_ragged  enforce_unique_id  both off
  1000         0.11s              0.18s     0.02s
  2000         0.42s              0.68s     0.03s
  4000         1.63s              2.91s     0.07s
  8000         6.19s             10.63s     0.11s

Doubling the rows quadruples the time in the first two columns. However, the last column is flat at about 14 microseconds per row.
So add_row itself is linear and the cost is these two checks. This will be even worse with more columns as each one is scanned on each insert.

I think both could be fixed by keeping an incremental check as the previous entries were already scanned:

• For raggedness, holding the column's common element length and an already-ragged flag answers from the appended element alone. The new element still has to be recursed into for nested raggedness, but that costs its own size rather than the table's.
• For the ids, a set answers in O(1), and the work is keeping it true when ids arrive by another route: passed at construction, appended directly through table.id.append, or read from a file where id.data is an h5py dataset and building the set would materialize the whole column. Caching only when the data is an in-memory list would be the conservative version.

Both checks can be made incremental without changing what they return, and I can open a pull request for each. What do you think? Is there a reason the full rescan has to stay?

Steps to Reproduce

import time

from hdmf.common import DynamicTable


def fill(num_rows, check_ragged=False, enforce_unique_id=False):
    table = DynamicTable(name="bench", description="")
    table.add_column(name="a", description="")
    start = time.perf_counter()
    for _ in range(num_rows):
        table.add_row(a=1.0, check_ragged=check_ragged, enforce_unique_id=enforce_unique_id)
    return time.perf_counter() - start


print(f"{'rows':>6}  {'check_ragged':>12}  {'enforce_unique_id':>17}  {'both off':>8}")
for num_rows in (1_000, 2_000, 4_000, 8_000):
    ragged = fill(num_rows, check_ragged=True)
    unique = fill(num_rows, enforce_unique_id=True)
    neither = fill(num_rows)
    print(f"{num_rows:6d}  {ragged:11.2f}s  {unique:16.2f}s  {neither:7.2f}s")

Traceback

No traceback. The call completes, it is only slow.

Operating System

Linux

Python Version

3.12

Package Versions

hdmf 6.1.0 on python 3.12.3. The same two lines are on dev at dd22f161 and the numbers there are the same.