{"push_id":776471708,"size":377,"distinct_size":377,"ref":"refs/heads/simd","head":"787a21fe7c76143f76ae33722f68133a9e1e5f3c","before":"423f256d02b3eaddd31bdd4c88d16199a62ac475","commits":[{"sha":"3f1c7e1660c8f6d8d51ac70d39c7aa53f88542d1","author":{"email":"06a7813f879e3069b8b80d175ff4f9d3508d9379@gmail.com","name":"Andrew Paseltiner"},"message":"add `#[allow(unused_qualifications)]` to derived impls\n\ncloses #19102","distinct":true,"url":"https://api.github.com/repos/huonw/rust/commits/3f1c7e1660c8f6d8d51ac70d39c7aa53f88542d1"},{"sha":"c5a1d8c3db171a4351712c04e6ba6a4e4636a332","author":{"email":"5fe014533dc2118b313a9e0374041b564f2c4932@users.noreply.github.com","name":"Ulrik Sverdrup"},"message":"StrSearcher: Add tests for rfind(&str)\n\nAdd tests for .rfind(&str), using the reverse searcher case for\nsubstring search.","distinct":true,"url":"https://api.github.com/repos/huonw/rust/commits/c5a1d8c3db171a4351712c04e6ba6a4e4636a332"},{"sha":"7ebae85bb8eac495bbc4a463319b23404fdc63a6","author":{"email":"5fe014533dc2118b313a9e0374041b564f2c4932@users.noreply.github.com","name":"Ulrik Sverdrup"},"message":"StrSearcher: Implement the full two way algorithm in reverse for rfind\n\nFix quadratic behavior in StrSearcher in reverse search with periodic\nneedles.\n\nThis commit adds the missing pieces for the \"short period\" case in\nreverse search. The short case will show up when the needle is literally\nperiodic, for example \"abababab\".\n\nTwo way uses a \"critical factorization\" of the needle: x = u v.\n\nSearching matches v first, if mismatch at character k, skip k forward.\nMatching u, if mismatch, skip period(x) forward.\n\nTo avoid O(mn) behavior after mismatch in u, memorize the already\nmatched prefix.\n\nThe short period case requires that |u| < period(x).\n\nFor the reverse search we need to compute a different critical\nfactorization x = u' v' where |v'| < period(x), because we are searching\nfor the reversed needle. A short v' also benefits the algorithm in\ngeneral.\n\nThe reverse critical factorization is computed quickly by using the same\nmaximal suffix algorithm, but terminating as soon as we have a location\nwith local period equal to period(x).\n\nThis adds extra fields crit_pos_back and memory_back for the reverse\ncase. The new overhead for TwoWaySearcher::new is low, and additionally\nI think the \"short period\" case is uncommon in many applications of\nstring search.\n\nThe maximal_suffix methods were updated in documentation and the\nalgorithms updated to not use !0 and wrapping add, variable left is now\n1 larger, offset 1 smaller.\n\nUse periodicity when computing byteset: in the periodic case, just\niterate over one period instead of the whole needle.\n\nExample before (rfind) after (twoway_rfind) benchmark shows the removal\nof quadratic behavior.\n\nneedle: \"ab\" * 100, haystack: (\"bb\" + \"ab\" * 100) * 100\n\n```\ntest periodic::rfind           ... bench:   1,926,595 ns/iter (+/- 11,390) = 10 MB/s\ntest periodic::twoway_rfind    ... bench:      51,740 ns/iter (+/- 66) = 386 MB/s\n```","distinct":true,"url":"https://api.github.com/repos/huonw/rust/commits/7ebae85bb8eac495bbc4a463319b23404fdc63a6"},{"sha":"2b82c072c75d64c434a62f185b67fb41028d6f71","author":{"email":"5fe014533dc2118b313a9e0374041b564f2c4932@users.noreply.github.com","name":"Ulrik Sverdrup"},"message":"StrSearcher: Improve inner loop in TwoWaySearcher::next, next_back\n\nThe innermost loop of TwoWaySearcher checks the boundary of the haystack\nvs position + needle.len(), and it checks the last byte of the needle\nagainst the byteset.\n\nIf these two steps are combined by using the indexing of the last\nneedle byte's position as bounds check, the algorithm improves its\nthroughput. We improve the innermost loop by reducing the number of\ninstructions used, and elminating the panic case for the checked\nindexing that was previously used.\n\nSelected benchmarks from the external/workspace testsuite. Benchmarks\nimprove across the board.\n\n```\nbefore:\n\ntest bb_in_aa::twoway_find                  ... bench:       4,229 ns/iter (+/- 1,305) = 23646 MB/s\ntest bb_in_aa::twoway_rfind                 ... bench:       3,873 ns/iter (+/- 101) = 25819 MB/s\ntest short_1let_long::twoway_find           ... bench:       7,075 ns/iter (+/- 29) = 360 MB/s\ntest short_1let_long::twoway_rfind          ... bench:       6,640 ns/iter (+/- 79) = 384 MB/s\ntest short_2let_long::twoway_find           ... bench:       3,823 ns/iter (+/- 16) = 667 MB/s\ntest short_2let_long::twoway_rfind          ... bench:       3,774 ns/iter (+/- 44) = 675 MB/s\ntest short_3let_long::twoway_find           ... bench:       3,582 ns/iter (+/- 47) = 712 MB/s\ntest short_3let_long::twoway_rfind          ... bench:       3,616 ns/iter (+/- 34) = 705 MB/s\n\nwith this commit:\n\ntest bb_in_aa::twoway_find                  ... bench:       2,952 ns/iter (+/- 20) = 33875 MB/s\ntest bb_in_aa::twoway_rfind                 ... bench:       2,939 ns/iter (+/- 99) = 34025 MB/s\ntest short_1let_long::twoway_find           ... bench:       4,593 ns/iter (+/- 4) = 555 MB/s\ntest short_1let_long::twoway_rfind          ... bench:       4,592 ns/iter (+/- 76) = 555 MB/s\ntest short_2let_long::twoway_find           ... bench:       2,804 ns/iter (+/- 3) = 909 MB/s\ntest short_2let_long::twoway_rfind          ... bench:       2,807 ns/iter (+/- 40) = 908 MB/s\ntest short_3let_long::twoway_find           ... bench:       3,105 ns/iter (+/- 120) = 821 MB/s\ntest short_3let_long::twoway_rfind          ... bench:       3,019 ns/iter (+/- 50) = 844 MB/s\n```\n\n- `bb_in_aa`: fast skip due to byteset filter loop improves.\n- 1/2/3let: Searches for 1, 2, or 3 ascii bytes improves.","distinct":true,"url":"https://api.github.com/repos/huonw/rust/commits/2b82c072c75d64c434a62f185b67fb41028d6f71"},{"sha":"f4ea3928aca448788e0d3abc05d7ece832278f80","author":{"email":"b4ca99620bc3ce71755808750a1d24996316715f@outlook.com","name":"Garming Sam"},"message":"Introduce callback to resolver\n\nSets a flag to pass through the rest of the walker.","distinct":true,"url":"https://api.github.com/repos/huonw/rust/commits/f4ea3928aca448788e0d3abc05d7ece832278f80"},{"sha":"ff6dd5c24b0da35d5ad1e0e20082f3d62b74b190","author":{"email":"b4ca99620bc3ce71755808750a1d24996316715f@outlook.com","name":"Garming Sam"},"message":"Avoid change to current module on escape from callback","distinct":true,"url":"https://api.github.com/repos/huonw/rust/commits/ff6dd5c24b0da35d5ad1e0e20082f3d62b74b190"},{"sha":"251696ed0da7c2c829de0b61f1ea930b815cfbd2","author":{"email":"b4ca99620bc3ce71755808750a1d24996316715f@outlook.com","name":"Garming Sam"},"message":"Remove unused language items","distinct":true,"url":"https://api.github.com/repos/huonw/rust/commits/251696ed0da7c2c829de0b61f1ea930b815cfbd2"},{"sha":"8b98256f64362cc524952c0641f4e23c27937db1","author":{"email":"b4ca99620bc3ce71755808750a1d24996316715f@outlook.com","name":"Garming Sam"},"message":"Remove some duplicated code with new create_resolver","distinct":true,"url":"https://api.github.com/repos/huonw/rust/commits/8b98256f64362cc524952c0641f4e23c27937db1"},{"sha":"ed9f8f83c90e995ad41f8c3c26f81d34900ec631","author":{"email":"b4ca99620bc3ce71755808750a1d24996316715f@outlook.com","name":"Garming Sam"},"message":"Expose more of the save analysis module","distinct":true,"url":"https://api.github.com/repos/huonw/rust/commits/ed9f8f83c90e995ad41f8c3c26f81d34900ec631"},{"sha":"fdba872944675a2c2aa146ab3caadbad14452e97","author":{"email":"b4ca99620bc3ce71755808750a1d24996316715f@outlook.com","name":"Garming Sam"},"message":"Add a proper comment for create_resolver","distinct":true,"url":"https://api.github.com/repos/huonw/rust/commits/fdba872944675a2c2aa146ab3caadbad14452e97"},{"sha":"c67a34b9e509b76ff145526f28a20f9495c2ab61","author":{"email":"b4ca99620bc3ce71755808750a1d24996316715f@outlook.com","name":"Garming Sam"},"message":"Binary ops should add parenthesis to each side\n\nOtherwise, we get (1 + 2) * 3 looking like 1 + 2 * 3","distinct":true,"url":"https://api.github.com/repos/huonw/rust/commits/c67a34b9e509b76ff145526f28a20f9495c2ab61"},{"sha":"c0c6af7f073620aacfb103c070e997a8d50b7201","author":{"email":"b4ca99620bc3ce71755808750a1d24996316715f@outlook.com","name":"Garming Sam"},"message":"Add operator precedence for pretty printer\n\nPreviously it just added parentheses in excess.\ne.g. ((1 + 2) + 3) + 4","distinct":true,"url":"https://api.github.com/repos/huonw/rust/commits/c0c6af7f073620aacfb103c070e997a8d50b7201"},{"sha":"6a51de0a0a846524dc76b027f52f0afec1597383","author":{"email":"b4ca99620bc3ce71755808750a1d24996316715f@outlook.com","name":"Garming Sam"},"message":"Casts are a type of binop\n\nThis just adds paren following the same cases as before","distinct":true,"url":"https://api.github.com/repos/huonw/rust/commits/6a51de0a0a846524dc76b027f52f0afec1597383"},{"sha":"22baa46f784856b6d6bb4374bcc3fb4b66bb8097","author":{"email":"b4ca99620bc3ce71755808750a1d24996316715f@outlook.com","name":"Garming Sam"},"message":"Avoid adding extra paren with two casts","distinct":true,"url":"https://api.github.com/repos/huonw/rust/commits/22baa46f784856b6d6bb4374bcc3fb4b66bb8097"},{"sha":"fc9ecae4442ba39ed1474a129d10bd37c7fdab00","author":{"email":"b4ca99620bc3ce71755808750a1d24996316715f@outlook.com","name":"Garming Sam"},"message":"Modify the callback to be run from a macro","distinct":true,"url":"https://api.github.com/repos/huonw/rust/commits/fc9ecae4442ba39ed1474a129d10bd37c7fdab00"},{"sha":"28d5d2fad06688164946cea250e23516cabc3541","author":{"email":"06a7813f879e3069b8b80d175ff4f9d3508d9379@gmail.com","name":"Andrew Paseltiner"},"message":"Remove transmute from `btree::node::Node::as_slices_internal_mut`\n\nCloses #27620.","distinct":true,"url":"https://api.github.com/repos/huonw/rust/commits/28d5d2fad06688164946cea250e23516cabc3541"},{"sha":"2d4e07edb5007fc8f230bde5c38f8e538de433cb","author":{"email":"1d6e1cf70ec6f9ab28d3ea4b27a49a77654d370e@timnn.me","name":"Tim Neumann"},"message":"Fix #23808: dead_code lint: visit types in paths","distinct":true,"url":"https://api.github.com/repos/huonw/rust/commits/2d4e07edb5007fc8f230bde5c38f8e538de433cb"},{"sha":"b87c2926271dcf3d0556b16ae3ea8fec75058d4a","author":{"email":"d8304a100f9eb6d8398a1b27f47b5aa4c1c0b0be@gmail.com","name":"Ariel Ben-Yehuda"},"message":"be more robust to bogus items in struct patterns/constructors\n\nFixes #27815","distinct":true,"url":"https://api.github.com/repos/huonw/rust/commits/b87c2926271dcf3d0556b16ae3ea8fec75058d4a"},{"sha":"2f84173f2c359041d364579d17a1adc8c6569a44","author":{"email":"b1db332606efda9d9987ee09ce352e2a96143e72@gmail.com","name":"Guillaume Gomez"},"message":"Add E0103 error explanation","distinct":true,"url":"https://api.github.com/repos/huonw/rust/commits/2f84173f2c359041d364579d17a1adc8c6569a44"},{"sha":"8ef395fb7fba3b38e4b6aa4ff0d4b0db1524ee47","author":{"email":"b1db332606efda9d9987ee09ce352e2a96143e72@gmail.com","name":"Guillaume Gomez"},"message":"Add E0369 error explanation","distinct":true,"url":"https://api.github.com/repos/huonw/rust/commits/8ef395fb7fba3b38e4b6aa4ff0d4b0db1524ee47"}]}