Skip to content

Instantly share code, notes, and snippets.

@farooqkz
Last active May 10, 2021 15:17
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save farooqkz/d061b467e3fa06044672da68d1d1600b to your computer and use it in GitHub Desktop.
Save farooqkz/d061b467e3fa06044672da68d1d1600b to your computer and use it in GitHub Desktop.
Warshall algorithm calculating transitive closure
// Code by Rust beginner, Farooq Karimi Zadeh
// Under CC0 1.0
// Warning! Code might not be idiomatic
fn main() {
let mut bin_matrix = [
[0, 1, 0, 0],
[1, 0, 1, 0],
[0, 0, 0, 1],
[0, 0, 0, 0]
];
const N:u32 = 300_000;
for _dummy in 0..N {
for k in 0..bin_matrix.len() {
let the_clone = bin_matrix;
for (i, row) in bin_matrix.iter_mut().enumerate() {
for (j, value) in row.iter_mut().enumerate() {
if *value == 0 {
*value = the_clone[i][k] & the_clone[k][j];
}
}
}
}
}
println!("{:?}", bin_matrix);
}
@farooqkz
Copy link
Author

[19:37:40]:~/rs$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   36 bits physical, 48 bits virtual
CPU(s):                          4
On-line CPU(s) list:             0-3
Thread(s) per core:              2
Core(s) per socket:              2
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           58
Model name:                      Intel(R) Core(TM) i5-3230M CPU @ 2.60GHz
Stepping:                        9
CPU MHz:                         1196.110
CPU max MHz:                     3200.0000
CPU min MHz:                     1200.0000
BogoMIPS:                        5183.04
Virtualization:                  VT-x
L1d cache:                       64 KiB
L1i cache:                       64 KiB
L2 cache:                        512 KiB
L3 cache:                        3 MiB
NUMA node0 CPU(s):               0-3
Vulnerability Itlb multihit:     KVM: Mitigation: Split huge pages
Vulnerability L1tf:              Mitigation; PTE Inversion; VMX condition
                                 al cache flushes, SMT vulnerable
Vulnerability Mds:               Mitigation; Clear CPU buffers; SMT vulne
                                 rable
Vulnerability Meltdown:          Mitigation; PTI
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass dis
                                 abled via prctl and seccomp
Vulnerability Spectre v1:        Mitigation; usercopy/swapgs barriers and
                                  __user pointer sanitization
Vulnerability Spectre v2:        Mitigation; Full generic retpoline, IBPB
                                  conditional, IBRS_FW, STIBP conditional
                                 , RSB filling
Vulnerability Srbds:             Vulnerable: No microcode
Vulnerability Tsx async abort:   Not affected
Flags:   ...
[19:38:01]:~/rs$ time ./warshall 
[[1, 1, 1, 1], [1, 1, 1, 1], [0, 0, 0, 1], [0, 0, 0, 0]]

real	0m1.271s
user	0m1.266s
sys	0m0.000s

See https://gist.github.com/farooqkz/a6d6ac3cacdf06af1907952888acc5c2 for Python version

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment