Optimization #4747
openapp-layer: make tx iterator a mandatory part of the API
Added by Victor Julien about 3 years ago. Updated over 1 year ago.
Updated by Victor Julien about 3 years ago
- Related to Bug #4741: Quadratic complexity in modus due to missing tx_iterator added
Updated by Philippe Antoine about 3 years ago
Maybe a macro would be easier as export_tx_data_get
or such
A trait would need to be implemented for each State
structure with a function returning an iterator over a list of Transactions
traits which can return an id
I do not know if it has performance implications (like type assertions at runtime, or more memory...)
Updated by Jason Ish about 3 years ago
Why make it a mandatory part of the API? I think it should be in the description? Simply to avoid performance issues?
Updated by Jason Ish about 3 years ago
Philippe Antoine wrote in #note-2:
Maybe a macro would be easier as
export_tx_data_get
or suchA trait would need to be implemented for each
State
structure with a function returning an iterator over a list ofTransactions
traits which can return an id
I do not know if it has performance implications (like type assertions at runtime, or more memory...)
First we'd just make the iterator non-optional in the parser registration on the Rust side, at least forcing a C binding to be created.
But I think a generic function will take care of this without the overhead of a trait. Last I tried using traits on the actual parser object I hit up against some FFI issues with trait pointers, probably worth revisiting, but for this, I think a generic utility functions is all thats needed.
Create a trait, Transaction
that exposes a get_id
method and implement this for each ProtocolTransaction
struct. Then we can make a utility function that is generic over Transaction
, something like:
fn get_iter<'a, T: Transaction>(transactions: &'a[T], min_tx_id: u64, state: &mut u64) -> Option<(&'a T, u64, bool)> { let mut index = *state as usize; let len = transactions.len(); while index < len { let tx = &transactions[index]; if tx.get_id() < min_tx_id + 1 { index += 1; continue; } *state = index as u64; return Some((tx, tx.get_id() - 1, (len - index) > 1)); } None }
Updated by Jason Ish about 3 years ago
Updated by Jason Ish about 3 years ago
Philippe Antoine wrote in #note-2:
Maybe a macro would be easier as
export_tx_data_get
or suchA trait would need to be implemented for each
State
structure with a function returning an iterator over a list ofTransactions
traits which can return an id
I do not know if it has performance implications (like type assertions at runtime, or more memory...)
If you can avoid dynamic dispatch then generally the performance hit happens at compile time rather than runtime. If you see my PR (https://github.com/OISF/suricata/pull/6519) the traits specify behaviour where the function call overhead will be erased after optimization, then the generic function uses static dispatch for the generic functions, meaning its acting more like a macro with a separate implementation being generated and compiled for each type. So I think we can do this without worrying about runtime performance overhead.
Updated by Jason Ish over 2 years ago
- Related to Bug #5314: ftp: quadratic complexity for tx iterator with linked list added
Updated by Philippe Antoine over 1 year ago
- Assignee set to OISF Dev
- Target version set to 8.0.0-beta1
Only SSH seems to have None (and it has ever only one transaction)