r/adventofcode • u/willkill07 • Dec 05 '16
Upping the Ante [2016 - Day 5] [C++] STAYING ON TARGET with Parallelism
How to stay on target: compute MD5s in parallel.
You can get away with processing a block of N in parallel because there won't be collisions in a given block of small enough size (avalanche effect).
Running on my 2013 MacBook Pro (unplugged), compiled using AppleClang with optimization flags, I compute part 2 in a little over 1.1 seconds.
Code: https://github.com/willkill07/adventofcode2016/blob/master/src/Day05.cpp
Mandatory bonus video: http://imgur.com/qCSxwDf
1
u/red75prim Dec 06 '16 edited Dec 06 '16
Rust, using channels: http://pastebin.com/r2CaRS4G
0.8 sec on Core i7 4790(HT) @ 4GHz
ETA: I cannot build your project. If you want to compare to mine, you can do:
Install Rust thru package manager or from https://www.rust-lang.org/ru-RU/downloads.html
In home dir do
cargo new aoc2016day5 --binCopy contents from pastebin into
~/aoc2016day5/src/main.rsAdd following lines to~/aoc2016day5/cargo.tomlregex = "0.1" rust-crypto = "0.2" num_cpus = "1.2"cd ~/aoc2016day5 ; cargo run --release
1
u/willkill07 Dec 06 '16
I get an error when running:
$ RUST_BACKTRACE=1 cargo run --release Finished release [optimized] target(s) in 0.0 secs Running `target/release/aoc2016day5` Starting 8 threads Decoding: f2c730e5 f2c730e5 thread 'thread 'thread '<unnamed><unnamed><unnamed>' panicked at '' panicked at '' panicked at 'called `Result::unwrap()` on an `Err` value: RecvErrorcalled `Result::unwrap()` on an `Err` value: RecvErrorcalled `Result::unwrap()` on an `Err` value: RecvError', ', ', src/libcore/result.rssrc/libcore/result.rssrc/libcore/result.rs:::799799799 stack backtrace:I fixed my error, so you should be able to pull and compile again
1
u/red75prim Dec 06 '16
I didn't bother to kill worker threads explicitly, errors happen when main thread is already stopped, so the result is not affected.
Linux seems to wake worker threads before termination. Windows doesn't.
1
u/willkill07 Dec 06 '16
I'm running on macOS 10.12 and installed rust with
brew install rust. You should kill them explicitly ;)1
u/red75prim Dec 06 '16 edited Dec 06 '16
http://pastebin.com/pXLibpkw Done
ETA: disregard this. I forgot to call join. Wait a minute.
1
1
u/willkill07 Dec 06 '16
I will also note that the desktop 4790K (4.0GHz) is way beefier than my mobile 4960HQ (2.6GHz) in terms of compute performance. Memory bandwidth I have the advantage due to the 128MB of embedded DRAM.
1
u/red75prim Dec 06 '16
Well, I almost got your project built, but I'm on windows, so it's rather difficult. Linux subsystem for Windows has cmake 2.8.0, and native build tools lack getopts.h (and bzero, which was deprecated in 2001, wink)
1
u/willkill07 Dec 06 '16 edited Dec 06 '16
Your's runs in the same time as mine on my system. (<0.5% variation with execution times being negligible) (~1150ms to do both parts).
I modified my solution to complete both parts "in parallel" instead of subsequent executions.
I also updated the md5 implementation to have no references to bzero (blame XNU for that -- I'm just using their implementation)
#include "Solution.hpp" #include "io.hpp" #include "md5.hpp" #include <thread> template <> void solve<Day05>(bool part2, std::istream& is, std::ostream& os) { std::string pw0{"________"}, pw1{"________"}, in{io::as_string(is)}; int cores(std::thread::hardware_concurrency()), d0{0}, d1{0}; std::vector<std::thread> threads; for (int c{0}; c < cores; ++c) threads.emplace_back([part2, cores, &d0, &d1, &pw0, &pw1, &os](std::string in, int index) { const static std::string lookup{"0123456789abcdef"}; int length(in.size()); in.resize(in.size() + 10); while (d0 + d1 < 16) { int n0{-1}, n1{-1}, p0{d0}, p1{-1}, len{length - 1 + snprintf(&in[length - 1], in.size(), "%d", index)}; auto digest = md5((uint8_t*)in.data(), len); if ((digest[0] & 0x00F0FFFF) == 0) { // leading zero mask n0 = p1 = (digest[0] & 0x000F0000) >> 16; // digest[5] extraction n1 = digest[0] >> 28; // digest[6] extraction if (p1 > 7 || pw1[p1] != '_' || pw1.find(lookup[n1]) != std::string::npos) n1 = -1; } if (n0 != -1 && d0 < 8) ++d0, pw0[p0] = lookup[n0]; if (n1 != -1 && d1 < 8) ++d1, pw1[p1] = lookup[n1]; index += cores; } }, in, c); for (auto& t : threads) t.join(); os << pw0 << ' ' << pw1 << std::endl; }1
u/red75prim Dec 06 '16
This should shave off a couple of milliseconds http://pastebin.com/DC5bySL3
OK. Message passing is on par with data sharing. Good. I'm content.
Heh, XNU is Not Unix, and is not posix, apparently.
1
u/willkill07 Dec 06 '16
This version runs 1ms consistently faster :)
1
u/red75prim Dec 06 '16
Windows has longer scheduling time slices, it seems. I've got around 20ms decrease of runtime.
2
1
u/mmstick Dec 06 '16
I was going to compare your parallel implementation to mine in Rust but I'm getting a linker error when trying to compile your solution.