{"action":"created","issue":{"url":"https://api.github.com/repos/indigits/scirust/issues/19","labels_url":"https://api.github.com/repos/indigits/scirust/issues/19/labels{/name}","comments_url":"https://api.github.com/repos/indigits/scirust/issues/19/comments","events_url":"https://api.github.com/repos/indigits/scirust/issues/19/events","html_url":"https://github.com/indigits/scirust/pull/19","id":99224928,"number":19,"title":"Block multiplication of matrices.","user":{"login":"dbalchev","id":3525601,"avatar_url":"https://avatars.githubusercontent.com/u/3525601?v=3","gravatar_id":"","url":"https://api.github.com/users/dbalchev","html_url":"https://github.com/dbalchev","followers_url":"https://api.github.com/users/dbalchev/followers","following_url":"https://api.github.com/users/dbalchev/following{/other_user}","gists_url":"https://api.github.com/users/dbalchev/gists{/gist_id}","starred_url":"https://api.github.com/users/dbalchev/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dbalchev/subscriptions","organizations_url":"https://api.github.com/users/dbalchev/orgs","repos_url":"https://api.github.com/users/dbalchev/repos","events_url":"https://api.github.com/users/dbalchev/events{/privacy}","received_events_url":"https://api.github.com/users/dbalchev/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":3,"created_at":"2015-08-05T15:00:19Z","updated_at":"2015-08-05T16:02:37Z","closed_at":"2015-08-05T15:27:32Z","pull_request":{"url":"https://api.github.com/repos/indigits/scirust/pulls/19","html_url":"https://github.com/indigits/scirust/pull/19","diff_url":"https://github.com/indigits/scirust/pull/19.diff","patch_url":"https://github.com/indigits/scirust/pull/19.patch"},"body":"I've wrote a function multiplying matrices by blocks. It should to be faster on larger matrices due to cache related issues of the simple multiplication function. It doesn't change the memory layout of the matrix.\r\n\r\nI've tested the performance of both the simple (previous) and block multiplication of square matrices. For block size of 16 (it performed best on my computer) the block multiplication is outperforming the simple multiplication when matrix size is 32x32 and when the matrix size is 256x256 it's twice as fast as simple multiplication. I've copied the bench output at the end of this post.\r\n\r\nPS: This is my first pull request, so i doubt it's well-formed. I wasn't sure if I had to raise an issue before making a pullrequest . Also I'm not sure if the code is readable enough.\r\n\r\n\r\nThis is the bench output on my Intel i7-3740QM PC.\r\ntest matrix::transpose::matrix_transpose::bench::bench_gram_optimized\r\n     ... bench:   3,174,322 ns/iter (+/- 169,171)\r\ntest matrix::transpose::matrix_transpose::bench::bench_gram_simple\r\n     ... bench:   6,123,006 ns/iter (+/- 241,711)\r\ntest matrix::transpose::matrix_transpose::bench::bench_multiply_0001_block\r\n     ... bench:         273 ns/iter (+/- 78)\r\ntest matrix::transpose::matrix_transpose::bench::bench_multiply_0001_simple\r\n     ... bench:          32 ns/iter (+/- 2)\r\ntest matrix::transpose::matrix_transpose::bench::bench_multiply_0002_block\r\n     ... bench:         292 ns/iter (+/- 6)\r\ntest matrix::transpose::matrix_transpose::bench::bench_multiply_0002_simple\r\n     ... bench:          45 ns/iter (+/- 7)\r\ntest matrix::transpose::matrix_transpose::bench::bench_multiply_0004_block\r\n     ... bench:         378 ns/iter (+/- 11)\r\ntest matrix::transpose::matrix_transpose::bench::bench_multiply_0004_simple\r\n     ... bench:          99 ns/iter (+/- 14)\r\ntest matrix::transpose::matrix_transpose::bench::bench_multiply_0008_block\r\n     ... bench:         793 ns/iter (+/- 160)\r\ntest matrix::transpose::matrix_transpose::bench::bench_multiply_0008_simple\r\n     ... bench:         444 ns/iter (+/- 64)\r\ntest matrix::transpose::matrix_transpose::bench::bench_multiply_0016_block\r\n     ... bench:       3,378 ns/iter (+/- 274)\r\ntest matrix::transpose::matrix_transpose::bench::bench_multiply_0016_simple\r\n     ... bench:       2,602 ns/iter (+/- 174)\r\ntest matrix::transpose::matrix_transpose::bench::bench_multiply_0032_block\r\n     ... bench:      25,345 ns/iter (+/- 1,643)\r\ntest matrix::transpose::matrix_transpose::bench::bench_multiply_0032_simple\r\n     ... bench:      28,967 ns/iter (+/- 813)\r\ntest matrix::transpose::matrix_transpose::bench::bench_multiply_0064_block\r\n     ... bench:     192,730 ns/iter (+/- 23,921)\r\ntest matrix::transpose::matrix_transpose::bench::bench_multiply_0064_simple\r\n     ... bench:     242,750 ns/iter (+/- 4,406)\r\ntest matrix::transpose::matrix_transpose::bench::bench_multiply_0128_block\r\n     ... bench:   1,559,674 ns/iter (+/- 92,525)\r\ntest matrix::transpose::matrix_transpose::bench::bench_multiply_0128_simple\r\n     ... bench:   2,045,354 ns/iter (+/- 245,310)\r\ntest matrix::transpose::matrix_transpose::bench::bench_multiply_0256_block\r\n     ... bench:  12,406,499 ns/iter (+/- 498,650)\r\ntest matrix::transpose::matrix_transpose::bench::bench_multiply_0256_simple\r\n     ... bench:  27,055,370 ns/iter (+/- 753,259)\r\ntest matrix::transpose::matrix_transpose::bench::bench_multiply_0512_block\r\n     ... bench: 101,763,380 ns/iter (+/- 10,103,632)\r\ntest matrix::transpose::matrix_transpose::bench::bench_multiply_0512_simple\r\n     ... bench: 227,811,582 ns/iter (+/- 21,193,979)"},"comment":{"url":"https://api.github.com/repos/indigits/scirust/issues/comments/128050825","html_url":"https://github.com/indigits/scirust/pull/19#issuecomment-128050825","issue_url":"https://api.github.com/repos/indigits/scirust/issues/19","id":128050825,"user":{"login":"shailesh1729","id":8783308,"avatar_url":"https://avatars.githubusercontent.com/u/8783308?v=3","gravatar_id":"","url":"https://api.github.com/users/shailesh1729","html_url":"https://github.com/shailesh1729","followers_url":"https://api.github.com/users/shailesh1729/followers","following_url":"https://api.github.com/users/shailesh1729/following{/other_user}","gists_url":"https://api.github.com/users/shailesh1729/gists{/gist_id}","starred_url":"https://api.github.com/users/shailesh1729/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/shailesh1729/subscriptions","organizations_url":"https://api.github.com/users/shailesh1729/orgs","repos_url":"https://api.github.com/users/shailesh1729/repos","events_url":"https://api.github.com/users/shailesh1729/events{/privacy}","received_events_url":"https://api.github.com/users/shailesh1729/received_events","type":"User","site_admin":false},"created_at":"2015-08-05T16:02:37Z","updated_at":"2015-08-05T16:02:37Z","body":"Okay. So having block multiplication is justified for now. Here are some references for further study\r\n\r\nhttps://en.wikipedia.org/wiki/Strassen_algorithm\r\n\r\nhttps://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm\r\n\r\nNot  sure if it's worth the effort to try implementing these. If yes, then we can test them for matrices of pretty large size like 1024 x 1024 or 2048 x 2048. \r\n"}}