Performance Improvments

[adic3x]

As I understand DecodeOption is 7 (for now) flags. And it checked very often, on each value decoding. So use HashSet is VERY ineffective in this case. I think it may be replaced by bit logical operation. You can write it manually or use some crate like bitflags. The good news is we can impl all used methods from HashSet to new 'bitflags' struct and don't change anything in code (yes, it would be better to rewrite huge files to use a macro and in the case of DecodeOption to pass not a pointer, but directly the value (because it will be just u8 or u16), but this is not really important).

Maybe I could do this and make a pull request, but I want to know the author's opinion.

[stadelmanma]

You’re not wrong, a HashSet is definitely overkill in this case. Initially, if I’m remembering the code’s evolution correctly DecodeOptions used to only be checked a few times in the top level functions (e.g. validate files CRC or not) vs being checked in a loop like it is now.

I’m not opposed to a better solution, but I think I’d want to see some profiling evidence to quantify how much we’d stand to gain by increasing the complexity. Since the one advantage we do have here is a very simple, readable implementation. I also don’t want to add another dependency when it’s not solving some critical shortcoming.

[adic3x]

Ok, I do it and result... Nothing.

It started well: bitflags is proc macro which generates some boilerplate code to work with int as newtype pattern. Instead C style where flags may be any int in this case flags object can be created only in correct way. Methods which generates bitflag macro are same as HashSet methods: contains, insert and remove. It takes argument not by pointer but by value and returns different value but in our case it doesn't matter. So I replaced it easily.

Fit decoding            time:   [9.1238 ms 9.2037 ms 9.3109 ms]

It's from 9.1 ms to 9.5 ms on my i3 12100 with HashSet or bitflags.

The code of bench:

fn fit_decode() {
    let data: &[u8] = include_bytes!("../tests/fixtures/sample_mulitple_header.fit");
    let fit_data = fitparser::from_bytes(data).unwrap();
    assert_eq!(fit_data.len(), 3023);
}

fn criterion_benchmark(c: &mut criterion::Criterion) {
    c.bench_function("Fit decoding", |b| b.iter(|| fit_decode()));
}

criterion::criterion_group!(benches, criterion_benchmark);
criterion::criterion_main!(benches);

I use sample_mulitple_header as *.fit with some data.

Anyway I do pull request with two commits, first with bench (it may be useful, use cargo bench to run bench.) and second with migration from HashSet to bitflags but I think commit with migration must be ignored because it little breakes pub interface: from_reader_with_options now takes options: &DecodeOption instead options: &HashSet<DecodeOption>, I would fix this if there was a difference in performance but there is no difference.

It seems like Rust compiler can optimize HashSet (in fact enum with 7 options has size 1 byte) well:

https://godbolt.org/z/nEcxqMb5Y

Although it does do the operations to calculate the hash, they are apparently quite fast for a type that can have a maximum of 256 possible values. In fact, the implementation of HashSet could simply use 256 bytes of memory and not calculate the hash at all.

[stadelmanma]

Thanks for looking into this, the benchmark code is interesting and something I've not looked into before. I expanded your initial benchmark a bit just to see what would happen if I did it across all the test fixture files, although I'm not sure how useful it is. Doing repeated runs on my laptop I often see rather large "gains" or "losses" between back to back runs even though nothing in the code was touched. That's more than likely just a fact of having a 14 year old laptop vs something a bit beefier but if my benchmarks are inherently inconsistent even just because of my hardware then it's not helpful either.

use criterion::BenchmarkId;
use std::fs::File;
use std::io::Read;
use std::path::Path;

fn fit_decode(data: &[u8]) {
    let records = fitparser::from_bytes(data).unwrap();
    assert!(records.len() != 0)
}

fn criterion_benchmark(c: &mut criterion::Criterion) {
    let mut group = c.benchmark_group("parse_file");
    for entry in Path::new("./tests/fixtures").read_dir().unwrap() {
        let entry = entry.unwrap();
        let path = entry.path();
        let mut fp = File::open(entry.path()).unwrap();
        let mut buffer: Vec<u8> = Vec::new();
        fp.read_to_end(&mut buffer).unwrap();
        group.bench_with_input(
            BenchmarkId::from_parameter(path.to_string_lossy()),
            &buffer,
            |b, buffer| b.iter(|| fit_decode(buffer)),
        );
    }
    group.finish();
}

criterion::criterion_group!(benches, criterion_benchmark);
criterion::criterion_main!(benches);

[adic3x]

Hello again)

I want to share my experience. This is not criticism in any way, at most this is my modest code review)

So, earlier I used the PHP package:
https://github.com/adriangibbons/php-fit-file-analysis

My test case is ~30 .fit files. I read records basic data (lat, lon, altitude, distance, hr, power, cadence) and lap marks and a little process it (interpolate, remove peaks, smooth, check gps anomalies).

The PHP version passed the test case in 1600ms (1300ms w/o my processing, only read files by library).

The Rust version with this lib passed this test case in 400ms (with -O3). And 2000ms with debug/unoptimized. But it done in 2000ms with and without my processing. So my processing is cheap.

And I tried to write a file reading from scratch. I of course cheated by simply ignoring fields that are not important to me. As a result, I get 21ms for the test case (with -O3).

I want to give you some hints on where you can improve the performance. Of course if you want and if you need to, because even in its current state, your library looks robust and well documented. And your code is nicer to read than Garmin FIT SDK. Although of all the languages ​​that are there, I only know JavaScript 100%, so my experience with Garmin FIT SDK was depressing.

I already wrote about HashSet. And I tried to replace it, but it did not lead to a result because there are still many bottlenecks, and even optimizing one of them, we did not get a noticeable performance gain.

FitMessageDefenition also placed in HashMap in deserialize_message function. But as I understan .fit format we can have only 16 defenition in the same time. So you can use not even Vec but simple static sized array: [Option<FitMessageDefenition >; 16]. Or if you need to store overwritten defenitions - use Vec, push it and store in array vector index: [Option<usize>; 16] (use None as undeclared defenition).

Next thing is heap allocations and String. FitDataField contains two Strings. Some results from criterion:

// 7 ns
fn test_hashset(a: &std::collections::HashSet<u8>) -> bool {
    a.contains(&2)
}

// 0.28 ns
fn test_flag(a: u8) -> bool {
    a&2 == 2
}

// 26 ns
fn test_string_allocation() -> String {
    "distance".into()
}

// 0.26 ns
fn test_enum_allocation() -> X {
    X::A
}

enum X { A, B, C, Other(String) }

This bench may be incorrect because function call my take some time but String allocation isn't fast. And it requires dropping and deallocation. So it may be replaced by Cow<'static str, String> or by enum, something like:

#[repr(u8)]
enum FitDataFieldName {
    timestamp = 253,
    positionLat = 0,
    positionLong = 1,
    // ...
    // I'm not sure is it supported by .fit format, but it also possible:
    custom_defined_field(String) = 255,
}

Then for serialization you can impl serde::Serialize for FitDataFieldName where you get &'static str by pattern matching to write it as serialization data.

I don't really know what data structures can be used to efficiently handle an unknown number of fields. But using more efficient data structures that provide linear, "flat" access and fewer allocations may improve performance. For example, in my algorithm for the result I allocate a vector of length with a minimum capacity to avoid reallocations (I simply divide the size in bytes by a constant that I obtained experimentally).

Of course, changing something now may be difficult, but if you write it like this from the beginning - it will not be more difficult. For example, when I changed HashSet -> bitflags the code turned out to be almost completely identical.

And also, this may not provide an improvement in speed, but it is more convenient to calculate the CRC when parsing the header, once for the header and once for the data, so as not to "pollute" the functions with unnecessary logic. Single-Responsibility, bla-bla-bla.

P. S. Also PHP lib ignored CRC checking, so if I ignore it too - my test case completes in 10ms, 160x faster then PHP. BlazingFast™.

Good luck!

[stadelmanma]

Thanks for looking into this! It sounds like the CRC check might be the place to spend some time checking if I'm reading that correctly and you saw a speed decrease from 400ms -> 10ms? Or if nothing else, just adding a note in the README.

[adic3x]

Hmm, no. Let me explain)

*I remove some unimportant details and all checks from all code.

// Just basic struct
pub struct Frame {
    timestamp: u64,
    distance:  f64,
    lat:       i32,
    lon:       i32,
    hr:        u8,
    power:     u16,
    cadence:   u8,
    altitude:  f64,

    interpolated: bool,
}

There is how I used your lib with 400ms result:

pub fn read(mut cursor: &[u8]) {
    let mut processor = FitStreamProcessor::new();

    let mut decoded;

    let mut laps = Vec::new();
    let mut frames = Vec::new();

    while !cursor.is_empty() {
        (cursor, decoded) = processor.deserialize_next(cursor)?;
        match decoded {
            FitObject::Crc(..) => processor.reset(),
            FitObject::DataMessage(msg) => {
                let record = processor.decode_message(msg)?;

                match record.kind() {
                    MesgNum::Lap => if let Some(lapmark) = parse_lap(&record) { laps.push(lapmark); }
                    MesgNum::Record => parse_record(&record, &mut frames)?,
                    _ => (),
                }
            }
            _ => (),
        }
    }
}

fn parse_record(record: &FitDataRecord, frames: &mut Vec<Frame>) {
    let mut frame = Frame::default();

    for field in record.fields().iter() {
        macro_rules! process {
            // set field in frame
        }

        match field.name() {
            // custom timestamp processing
            "position_lat"  => process!(lat, SInt32, i32),
            "position_long" => process!(lon, SInt32, i32),
            "distance"      => process!(distance, Float64, f64),
            "heart_rate"    => process!(hr, UInt8, u8),
            "cadence"       => process!(cadence, UInt8, u8),
            "altitude"      => process!(altitude, Float64, f64),
            _ => (),
        }
    }

    // check previous frame timestamp and generate interpolated frames if it less by 2 or more

    frames.push(frame);
}

I write fit processing from from scratch and it works 21ms (w/ crc checking) and 10ms (w/o crc, just skip it, see below):

pub fn read(data: &[u8]) {
    let (mut cursor, fit_size) = parse_header(data)?; // INFO cursor = header_size

    const INIT: Option<Defenition> = None;
    let mut defenitions = [INIT; 16];

    let mut lapmarks = Vec::new();
    let mut frames = Vec::<Frame>::with_capacity(data.len() / FRAME_ALLOCATION_RATIO);

    while cursor < fit_size {
        let header_byte = *data.get(cursor).ok_or_else(|| eod(cursor))?; // read byte safe

        cursor += match (
            header_byte & COMPRESSED_HEADER_MASK == COMPRESSED_HEADER_MASK,
            header_byte & MESG_DEFINITION_MASK == MESG_DEFINITION_MASK,
        ) {
            (true, _) => todo!(), // not implemented yet, but will not affect perfomance
            (false, false) => {
                let defenition = defenitions[(header_byte & LOCAL_MESG_NUM_MASK) as usize].as_ref()
                    .ok_or(umt(cursor, header_byte))?; // is defenition is some

                match &defenition.msg_num {
                    MsgNum::Lap(v) => lapmarks.push(
                        parse_lap(&data[cursor..], v).map_err(|v| eod(cursor + v))?,
                    ),
                    MsgNum::Record(v) => parse_record(
                        &data[cursor..], v, &mut frames,
                    ).map_err(|v| eod(v))?,
                    MsgNum::Ignored => (),
                }

                defenition.size
            },
            (_, true) => {
                let (defenition, size) = parse_defenition(&data[cursor..]).map_err(|v| eod(v))?;
                defenitions[(header_byte & LOCAL_MESG_NUM_MASK) as usize] = Some(defenition);
                size
            },
        }
    }
}

fn parse_record(data: &[u8], defenition: &DefenitionRecord, frames: &mut Vec<Frame>) {
    let mut frame = Frame::default();

    macro_rules! process {
        // check is defenition field is some and try to read data and write it to frame
    }

    // timestamp
    process!(lat,        i32);
    process!(lon,        i32);
    process!(power,      u16);
    process!(cadence,    u8,);
    process!(hr,         u8,);
    process!(distance,   u32);
    process!(altitude,   u16);
    process!(altitude_e, u32);

    // interpolation

    frames.push(frame);
}

And Defenition:

enum MsgNum {
    Ignored,
    Lap(DefenitionLap) = 19,
    Record(DefenitionRecord) = 20,
}

struct DefenitionRecord {
    timestamp:  Option<usize>,
    distance:   Option<usize>,
    lat:        Option<usize>,
    lon:        Option<usize>,
    hr:         Option<usize>,
    power:      Option<usize>,
    cadence:    Option<usize>,
    altitude:   Option<usize>,
    altitude_e: Option<usize>,
}

struct DefenitionLap {
    timestamp: Option<usize>,
    trigger:   Option<usize>,
}

In my parse_defenition function I just check all necessary to me fields and save its offsets in Record as usize. I don't know if this approach can be applied if all possible types of fields need to be processed.

You won't be able to make the fastest code to read all possible fields. However, I'm sure your library can be speed up several times.

I think two String fields in FitDataField is one of bottlenecks:

pub struct FitDataField {
    name: String,
    number: u8,
    developer_data_index: Option<u8>, // None for built-in fields, for developer fields identifies which developer
    value: Value,
    units: String,
}

We testing your 'sample_mulitple_header.fit' earlier. It contains ~1500 records. It's ~15000 fields (very approximate). It's 30k heap allocations (and deallocations later).

My code doesn't use allocation at all (ok, lapmarks vector is very small and frames vector most likely will not use re-allocations). I don't use hash, instead I use flat, sized array to save Defenitions.

You need to process all fields, so it's unlikely that you'll be able to completely abandon dynamic data structures. However, replacing even a portion of them can make a significant difference in performance.

And do you really need to sort fields?

And about CRC:

fn parse_header(data: &[u8]) {
    let Some(header_size) = data.get(0) else { /*err*/ };
    let header_size = *header_size as usize;

    if header_size == 14 {
        let header_crc = u16::from_le_bytes(data[12..14].try_into().unwrap()); // previously I check data len 
        if header_crc != 0 && !check_crc(&data[0..12], header_crc) {
            /* err */
        }
    }

    let data_size = u32::from_le_bytes(data[4..8].try_into().unwrap()) as usize;

    let body_crc = u16::from_le_bytes(data[full_size .. full_size + CRC_LEN].try_into().unwrap()); // see above
    if !check_crc(&data[header_size..full_size], body_crc) {
        /* err */
    }
}

It's not about performance, I just don't "pollute" other functions by CRC updating.

I'm not saying it's easy (but some optimizations are really simple.). And I'm not saying you have to do it. I'm just telling you how you can probably do it if you want to.

[adic3x]

If you are interested - this solution works quite fast (only 3-4 times slower than mine, which ignores some fields and records). They use Go, which is slower than Rust and in my humble opinion has a very unpleasant syntax, but architecture is apparently quite successful.

https://github.com/muktihari/fit

Also:

https://github.com/roznet/fit-benchmarks