{"action":"created","issue":{"url":"https://api.github.com/repos/TeXitoi/benchmarksgame-rs/issues/58","repository_url":"https://api.github.com/repos/TeXitoi/benchmarksgame-rs","labels_url":"https://api.github.com/repos/TeXitoi/benchmarksgame-rs/issues/58/labels{/name}","comments_url":"https://api.github.com/repos/TeXitoi/benchmarksgame-rs/issues/58/comments","events_url":"https://api.github.com/repos/TeXitoi/benchmarksgame-rs/issues/58/events","html_url":"https://github.com/TeXitoi/benchmarksgame-rs/pull/58","id":211884138,"number":58,"title":"spectralnorm: rayon and de-vectorize","user":{"login":"cristicbz","id":801328,"avatar_url":"https://avatars1.githubusercontent.com/u/801328?v=3","gravatar_id":"","url":"https://api.github.com/users/cristicbz","html_url":"https://github.com/cristicbz","followers_url":"https://api.github.com/users/cristicbz/followers","following_url":"https://api.github.com/users/cristicbz/following{/other_user}","gists_url":"https://api.github.com/users/cristicbz/gists{/gist_id}","starred_url":"https://api.github.com/users/cristicbz/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cristicbz/subscriptions","organizations_url":"https://api.github.com/users/cristicbz/orgs","repos_url":"https://api.github.com/users/cristicbz/repos","events_url":"https://api.github.com/users/cristicbz/events{/privacy}","received_events_url":"https://api.github.com/users/cristicbz/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":8,"created_at":"2017-03-04T14:57:51Z","updated_at":"2017-03-26T20:21:54Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/TeXitoi/benchmarksgame-rs/pulls/58","html_url":"https://github.com/TeXitoi/benchmarksgame-rs/pull/58","diff_url":"https://github.com/TeXitoi/benchmarksgame-rs/pull/58.diff","patch_url":"https://github.com/TeXitoi/benchmarksgame-rs/pull/58.patch"},"body":"I got rid of all the `f64x2` and `usizex2` structs since the code wouldn't vectorize no matter how hard I tried. Unlike #51, I also completely get rid of chunking, letting rayon do all the work, using `par_iter_mut`.\r\n\r\nThis speeds up the code a little bit from 1.6s to 1.4s on my laptop"},"comment":{"url":"https://api.github.com/repos/TeXitoi/benchmarksgame-rs/issues/comments/289312055","html_url":"https://github.com/TeXitoi/benchmarksgame-rs/pull/58#issuecomment-289312055","issue_url":"https://api.github.com/repos/TeXitoi/benchmarksgame-rs/issues/58","id":289312055,"user":{"login":"cristicbz","id":801328,"avatar_url":"https://avatars1.githubusercontent.com/u/801328?v=3","gravatar_id":"","url":"https://api.github.com/users/cristicbz","html_url":"https://github.com/cristicbz","followers_url":"https://api.github.com/users/cristicbz/followers","following_url":"https://api.github.com/users/cristicbz/following{/other_user}","gists_url":"https://api.github.com/users/cristicbz/gists{/gist_id}","starred_url":"https://api.github.com/users/cristicbz/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cristicbz/subscriptions","organizations_url":"https://api.github.com/users/cristicbz/orgs","repos_url":"https://api.github.com/users/cristicbz/repos","events_url":"https://api.github.com/users/cristicbz/events{/privacy}","received_events_url":"https://api.github.com/users/cristicbz/received_events","type":"User","site_admin":false},"created_at":"2017-03-26T20:21:54Z","updated_at":"2017-03-26T20:21:54Z","body":"I managed to get this to vectorize, by using `[f64; 2]` and the `div_and_add` trick (with `#[inline(never)]`). It now runs at similar speed with C implementation. Please have a look and let me know if you have any comments before I submit this.\r\n\r\nI also tried a bunch of stuff just now and I'd like to document things.\r\n\r\nI adapted this version to use the `simd` crate (on nightly), giving this:\r\n\r\n```rust\r\n#![feature(cfg_target_feature)]\r\n\r\nextern crate simd;\r\nextern crate rayon;\r\n\r\nuse rayon::prelude::*;\r\n\r\n#[cfg(target_feature = \"sse2\")]\r\nuse simd::x86::sse2::f64x2;\r\n#[cfg(target_arch = \"aarch64\")]\r\nuse simd::aarch64::neon::f64x2;\r\n\r\n#[cfg(target_feature = \"sse2\")]\r\nuse simd::x86::sse2::u64x2;\r\n#[cfg(target_arch = \"aarch64\")]\r\nuse simd::aarch64::neon::u64x2;\r\n\r\n\r\nfn main() {\r\n    let n = std::env::args().nth(1)\r\n        .and_then(|n| n.parse().ok())\r\n        .unwrap_or(100);\r\n    let answer = spectralnorm(n);\r\n    println!(\"{:.9}\", answer);\r\n}\r\n\r\nfn spectralnorm(n: usize) -> f64 {\r\n    assert!(n % 2 == 0, \"only even lengths are accepted\");\r\n    let mut u = vec![f64x2::splat(1.0); n / 2];\r\n    let mut v = vec![f64x2::splat(0.0); n / 2];\r\n    let mut tmp = vec![f64x2::splat(0.0); n / 2];\r\n    for _ in 0..10 {\r\n        mult_AtAv(&u, &mut v, &mut tmp);\r\n        mult_AtAv(&v, &mut u, &mut tmp);\r\n    }\r\n    (dot(&u, &v) / dot(&v, &v)).sqrt()\r\n}\r\n\r\nfn mult_AtAv(v: &[f64x2], out: &mut [f64x2], tmp: &mut [f64x2]) {\r\n    mult(v, tmp, A);\r\n    mult(tmp, out, |i, j| A(j, i));\r\n}\r\n\r\n\r\nfn mult<F>(v: &[f64x2], out: &mut [f64x2], a: F)\r\n           where F: Fn(u64x2, u64x2) -> f64x2 + Sync {\r\n    out.par_iter_mut().enumerate().for_each(|(i, slot)| {\r\n        let i = 2 * i as u64;\r\n        let i0 = u64x2::splat(i);\r\n        let i1 = u64x2::splat(i + 1);\r\n        let slots = v.iter().enumerate().map(|(j, &x)| {\r\n            let j = u64x2::new(2 * j as u64, 2 * j as u64 + 1);\r\n            (x * a(i0, j), x * a(i1, j))\r\n        }).fold((f64x2::splat(0.0), f64x2::splat(0.0)), |s, x| (s.0 + x.0, s.1 + x.1));\r\n\r\n        *slot = f64x2::new(slots.0.extract(0) + slots.0.extract(1),\r\n                           slots.1.extract(0) + slots.1.extract(1));\r\n    });\r\n}\r\n\r\nfn A(i: u64x2, j: u64x2) -> f64x2 {\r\n    let s = i + j;\r\n    let r = ((s * (s + u64x2::splat(1)) >> 1u64) + i + u64x2::splat(1)).to_f64();\r\n    f64x2::splat(1.0) / r\r\n}\r\n\r\nfn dot(v: &[f64x2], u: &[f64x2]) -> f64 {\r\n    let r = u.iter()\r\n             .zip(v)\r\n             .map(|(&x, &y)| x * y)\r\n             .fold(f64x2::splat(0.0), |s, x| s + x);\r\n    r.extract(0) + r.extract(1)\r\n}\r\n```\r\n\r\nOn my computer, this versions runs a little bit faster than the C version (0.722s compared to 0.76s) Sadly, just adding the following dud implementations doesn't work.\r\n\r\n```rust\r\nuse std::ops::{Add, Shr, Mul, Div, Sub};\r\n\r\n\r\n#[derive(Copy, Clone, Debug, Default)]\r\npub struct f64x2(f64, f64);\r\n#[derive(Copy, Clone, Debug, Default)]\r\npub struct u64x2(u64, u64);\r\n\r\nimpl f64x2 {\r\n    pub fn new(x: f64, y: f64) -> f64x2 { f64x2(x, y) }\r\n    pub fn splat(x: f64) -> f64x2 { f64x2(x, x) }\r\n    pub fn extract(&self, i: u8) -> f64 {\r\n        match i {\r\n            0 => self.0,\r\n            1 => self.1,\r\n            _ => unreachable!(),\r\n        }\r\n    }\r\n}\r\n\r\nimpl Add for f64x2 {\r\n    type Output = Self;\r\n    fn add(self, rhs: Self) -> Self { f64x2(self.0 + rhs.0, self.1 + rhs.1) }\r\n}\r\nimpl Sub for f64x2 {\r\n    type Output = Self;\r\n    fn sub(self, rhs: Self) -> Self { f64x2(self.0 - rhs.0, self.1 - rhs.1) }\r\n}\r\nimpl Mul for f64x2 {\r\n    type Output = Self;\r\n    fn mul(self, rhs: Self) -> Self { f64x2(self.0 * rhs.0, self.1 * rhs.1) }\r\n}\r\nimpl Div for f64x2 {\r\n    type Output = Self;\r\n    fn div(self, rhs: Self) -> Self { f64x2(self.0 / rhs.0, self.1 / rhs.1) }\r\n}\r\n\r\n\r\nimpl u64x2 {\r\n    pub fn new(x: u64, y: u64) -> u64x2 { u64x2(x, y) }\r\n    pub fn splat(x: u64) -> u64x2 { u64x2(x, x) }\r\n    pub fn to_f64(self) -> f64x2 { f64x2(self.0 as f64, self.1 as f64) }\r\n}\r\n\r\nimpl Add for u64x2 {\r\n    type Output = Self;\r\n    fn add(self, rhs: Self) -> Self { u64x2(self.0 + rhs.0, self.1 + rhs.1) }\r\n}\r\nimpl Sub for u64x2 {\r\n    type Output = Self;\r\n    fn sub(self, rhs: Self) -> Self { u64x2(self.0 - rhs.0, self.1 - rhs.1) }\r\n}\r\nimpl Mul for u64x2 {\r\n    type Output = Self;\r\n    fn mul(self, rhs: Self) -> Self { u64x2(self.0 * rhs.0, self.1 * rhs.1) }\r\n}\r\nimpl Div for u64x2 {\r\n    type Output = Self;\r\n    fn div(self, rhs: Self) -> Self { u64x2(self.0 / rhs.0, self.1 / rhs.1) }\r\n}\r\nimpl Shr<u64> for u64x2 {\r\n    type Output = Self;\r\n    fn shr(self, rhs: u64) -> Self { u64x2(self.0 >> rhs, self.1 >> rhs) }\r\n}\r\n```\r\n\r\nbrings the runtime back to to `1.4s`. So that's annoying."}}
{"actor":{"display_login":"cristicbz"}}