A video-metadata extractor scans a sorted list of chapter timestamps on every request at a 1,200-request-per-minute peak - how do you remove that Python-level loop?

### What the scan is costing The original shape is something like a loop over the sorted marks that breaks when it passes the requested position. Every request pays interpreted iterations proportional to how far into the list the answer lies: an iterator advance, a comparison and a branch per element, all as bytecode. At a 1,200-request-per-minute peak - twenty requests a second - with a few hundred chapter marks per asset, that is a few thousand interpreted iterations a second. Noticeable, but the first thing to establish is whether it is the request's actual hotspot, which `cProfile` answers in minutes. ### Replacing the loop with the module The list is already ordered, which is the precondition the `bisect` module requires and never checks. `bisect.bisect_right(marks, pos)` returns the index where `pos` would be inserted to sit after any equal entries; `bisect.bisect_left(marks, pos)` returns the index where it would sit before them. The search is a binary search implemented in C, so per request you go from a scan proportional to the list length to a handful of comparisons with essentially no interpreter overhead - and unlike the built-in fold functions, this is not merely a constant-factor win: it changes the search from linear to logarithmic. The two variants matter and mixing them up is a real bug, not a style choice. For the last mark at or before a position, use `bisect_right(marks, pos) - 1`; that includes a mark exactly equal to `pos`. For the first mark strictly after it, use `bisect_right` without the subtraction. For the first mark at or after it, use `bisect_left`. Guard the boundaries: an index of `0` from `bisect_right` means the position precedes every mark, and subtracting one there would silently wrap around to the last element. The module compares using only `<`, that is the element type's `__lt__`. If the list is sorted by a different ordering than the one `<` implements - reverse order, or a locale-sensitive text ordering that does not match the default string comparison - the search returns a wrong index with no error at all. That silence is the main hazard, and it is why the list should be built once with `sorted()` and treated as an invariant rather than assumed to be ordered because it usually is. ### Searching records rather than bare values Real metadata rarely stores bare floats. Since Python 3.10 the bisect functions take a `key` argument, so a list of `(offset, title)` records can be searched by offset. Two details worth stating: the value you pass is the *key* value, not a record, and the key callable is applied only to the elements the binary search actually examines - about log2(n) of them - so even a Python-level key stays cheap. Before 3.10 the equivalent was keeping a parallel list of keys to search, then indexing the records with the result. ### Keeping the list sorted When new marks arrive, `bisect.insort` (and its explicit `insort_left` / `insort_right` forms) finds the position in log time and then calls the list's insert, which shifts the tail. That shift is O(n) in the number of elements - but it is a single contiguous block move of pointers in C, not an interpreted loop, so the constant is tiny and it stays comfortably fast for lists of thousands. The judgement is about the ratio: if reads dominate and inserts are occasional, `insort` is the right answer; if the workload is insert-heavy on a large list, batch the arrivals and re-sort once, or use a structure whose insert is genuinely logarithmic. What you must not do is call `sorted()` on every request - that is O(n log n) per request to serve a query that should cost log n. ### The judgement layer This is where a senior answer separates from a mechanical one. Measure first: with `cProfile` on the request path, the per-request parse of a locale-dependent timestamp format is a strong candidate to outweigh the scan, and if so the right fix is to parse once at ingest, store a numeric offset, and cache the sorted list per asset rather than to micro-optimise the search. Second, know the ceiling: this rewrite removes interpreted iterations, and once the loop is gone the remaining cost is whatever the surrounding Python does per request. If the profile then shows the numeric work itself dominating over large arrays, the next step is not another built-in but moving the whole operation into a compiled extension that works on contiguous buffers. Third, protect the invariant with a cheap assertion or a construction path that cannot produce an unsorted list, because a silently wrong index in a metadata extractor surfaces as subtly wrong output rather than as an exception.