search

rust-lang / datafrog

A lightweight Datalog engine in Rust
Apache License 2.0
796 stars 43 forks source link

Predicate leaper [WIP] #20

Closed frankmcsherry closed 5 years ago

frankmcsherry commented 5 years ago

This PR introduces treefrog::filters::{PrefixFilter, ValueFilter}, each of which implement Leaper. The first is constructed from a fn(&Tuple) -> bool and the second from a fn(&Tuple, &Val) -> bool. Each of them do the very simple action you would expect, the first one ruling out extensions based on prefix and the second filtering values down using the predicate.

nikomatsakis commented 5 years ago

Seems like a handi concept, though I'm not sure that I have a use for it yet =)

nikomatsakis commented 5 years ago

I just remembered that measuring wallclock is for suckers. Here is the perf stat data for the clap-rs run.

Before this branch

 Performance counter stats for 'cargo +nightly run -q --release -- -a DatafrogOpt inputs/clap-rs/app-parser-{{impl}}-add_defaults/':

          4,025.17 msec task-clock:u              #    1.000 CPUs utilized
                 0      context-switches:u        #    0.000 K/sec
                 0      cpu-migrations:u          #    0.000 K/sec
            59,305      page-faults:u             # 14734.161 M/sec
    15,758,451,927      cycles:u                  # 3915143.336 GHz
    23,096,903,211      instructions:u            #    1.47  insn per cycle
     5,605,560,844      branches:u                # 1392685923.975 M/sec
       183,745,828      branch-misses:u           #    3.28% of all branches

       4.025395892 seconds time elapsed

       3.921707000 seconds user
       0.091707000 seconds sys

After this branch

Trial 3
--------------------------------------------------
Directory: inputs/clap-rs/app-parser-{{impl}}-add_defaults/
Time: 3.089s

 Performance counter stats for 'cargo +nightly run -q --release -- -a DatafrogOpt inputs/clap-rs/app-parser-{{impl}}-add_defaults/':

          3,457.01 msec task-clock:u              #    1.000 CPUs utilized
                 0      context-switches:u        #    0.000 K/sec
                 0      cpu-migrations:u          #    0.000 K/sec
            67,908      page-faults:u             # 19643.622 M/sec
    14,628,191,302      cycles:u                  # 4231469.859 GHz
    23,038,912,035      instructions:u            #    1.57  insn per cycle
     5,589,209,698      branches:u                # 1616780358.114 M/sec
       184,352,921      branch-misses:u           #    3.30% of all branches

       3.456541405 seconds time elapsed

       3.328974000 seconds user
       0.117606000 seconds sys
frankmcsherry commented 5 years ago

Wait, but .. nothing changed in this branch other than some weird new predicate filters. :)

Is this for the &'a Val and Val unification?