{"payload":{"feedbackUrl":"https://github.com/orgs/community/discussions/53140","repo":{"id":850037186,"defaultBranch":"master","name":"buffered_reader","ownerLogin":"LucasSantos91","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2024-08-30T18:43:49.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/117400842?v=4","public":true,"private":false,"isOrgOwned":false},"refInfo":{"name":"","listCacheKey":"v0:1726872603.0","currentOid":""},"activityList":{"items":[{"before":null,"after":"534f58cabb754ee4d3493e748a23dac1fbb4445c","ref":"refs/heads/EqualRange","pushedAt":"2024-09-20T22:50:03.000Z","pushType":"branch_creation","commitsCount":0,"pusher":{"login":"LucasSantos91","name":"Lucas Santos","path":"/LucasSantos91","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/117400842?s=80&v=4"},"commit":{"message":"`std.equalRange`: Compute lower and upper bounds simultaneously\nThe current implementation of `equalRange` just calls `lowerRange` and `upperRange`, but a lot of\nthe work done by these two functions can be shared. Specifically, each iteration gives information about whether the lower bound or the upper bound can be tightened. This leads to fewer iterations and, since there is one comparison per iteration, fewer comparisons.\nImplementation adapted from [GCC](https://github.com/gcc-mirror/gcc/blob/519ec1cfe9d2c6a1d06709c52cb103508d2c42a7/libstdc%2B%2B-v3/include/bits/stl_algo.h#L2063).\nThis sample demonstrates the difference between the current implementation and mine:\n\n```zig\nfn S(comptime T: type) type {\n    return struct {\n        needle: T,\n        count: *usize,\n\n        pub fn order(context: @This(), item: T) std.math.Order {\n            context.count.* += 1;\n            return std.math.order(item, context.needle);\n        }\n        pub fn orderLength(context: @This(), item: []const u8) std.math.Order {\n            context.count.* += 1;\n            return std.math.order(item.len, context.needle);\n        }\n    };\n}\npub fn main() !void {\n    var count: usize = 0;\n\n    try std.testing.expectEqual(.{ 0, 0 }, equalRange(i32, &[_]i32{}, S(i32){ .needle = 0, .count = &count }, S(i32).order));\n    try std.testing.expectEqual(.{ 0, 0 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 0, .count = &count }, S(i32).order));\n    try std.testing.expectEqual(.{ 0, 1 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 2, .count = &count }, S(i32).order));\n    try std.testing.expectEqual(.{ 2, 2 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 5, .count = &count }, S(i32).order));\n    try std.testing.expectEqual(.{ 2, 3 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 8, .count = &count }, S(i32).order));\n    try std.testing.expectEqual(.{ 5, 6 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 64, .count = &count }, S(i32).order));\n    try std.testing.expectEqual(.{ 6, 6 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 100, .count = &count }, S(i32).order));\n    try std.testing.expectEqual(.{ 2, 6 }, equalRange(i32, &[_]i32{ 2, 4, 8, 8, 8, 8, 15, 22 }, S(i32){ .needle = 8, .count = &count }, S(i32).order));\n    try std.testing.expectEqual(.{ 2, 2 }, equalRange(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, S(u32){ .needle = 5, .count = &count }, S(u32).order));\n    try std.testing.expectEqual(.{ 1, 1 }, equalRange(f32, &[_]f32{ -54.2, -26.7, 0.0, 56.55, 100.1, 322.0 }, S(f32){ .needle = -33.4, .count = &count }, S(f32).order));\n    try std.testing.expectEqual(.{ 3, 5 }, equalRange(\n        []const u8,\n        &[_][]const u8{ \"Mars\", \"Venus\", \"Earth\", \"Saturn\", \"Uranus\", \"Mercury\", \"Jupiter\", \"Neptune\" },\n        S(usize){ .needle = 6, .count = &count },\n        S(usize).orderLength,\n    ));\n\n    std.debug.print(\"Count: {}\\n\", .{count});\n}\n```\nFor each comparison, we bump the count. With the current implementation, we get 57 comparisons. With mine, we get 43.\n\nWith contributions from @Olvilock.\nThis is my second attempt at this, since I messed up the [first one](https://github.com/ziglang/zig/pull/21290).","shortMessageHtmlLink":"<code>std.equalRange</code>: Compute lower and upper bounds simultaneously"}},{"before":"fdbc31e864b0d48a02e45311ee26e21451874161","after":"7ca4ee151d840ea3159fd9e1bf57183d3bba38cd","ref":"refs/heads/equalRange","pushedAt":"2024-09-20T22:28:04.000Z","pushType":"push","commitsCount":1,"pusher":{"login":"LucasSantos91","name":"Lucas Santos","path":"/LucasSantos91","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/117400842?s=80&v=4"},"commit":{"message":"Fixed interpretation of the `Order` returned by the `compareFn`.","shortMessageHtmlLink":"Fixed interpretation of the <code>Order</code> returned by the <code>compareFn</code>."}},{"before":"8f742ece1e8008617cc40a01d2feb8fa0152f8de","after":"fdbc31e864b0d48a02e45311ee26e21451874161","ref":"refs/heads/equalRange","pushedAt":"2024-09-20T22:26:46.000Z","pushType":"push","commitsCount":264,"pusher":{"login":"LucasSantos91","name":"Lucas Santos","path":"/LucasSantos91","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/117400842?s=80&v=4"},"commit":{"message":"Merge branch 'equalRange' of https://github.com/LucasSantos91/buffered_reader into equalRange","shortMessageHtmlLink":"Merge branch 'equalRange' of <a href=\"https://github.com/LucasSantos91/buffered_reader\">https://github.com/LucasSantos91/buffere…</a>"}},{"before":"bb7baa6fb09d4ded8d79874693f8f125f9a6bb26","after":"e4b1e02c585cdbbad24f67535239636fc1f33f1e","ref":"refs/heads/master","pushedAt":"2024-09-20T21:27:23.000Z","pushType":"force_push","commitsCount":0,"pusher":{"login":"LucasSantos91","name":"Lucas Santos","path":"/LucasSantos91","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/117400842?s=80&v=4"},"commit":{"message":"Fix tests.\nThe tests for the BufferedReader wrongfully expected read to behave like readAll. That is, they didn't expect partial reads.","shortMessageHtmlLink":"Fix tests."}},{"before":"0df1d78d78f21ba27c4f35e02d26deb5af1af4d0","after":"8f742ece1e8008617cc40a01d2feb8fa0152f8de","ref":"refs/heads/equalRange","pushedAt":"2024-09-03T21:52:51.000Z","pushType":"push","commitsCount":1,"pusher":{"login":"LucasSantos91","name":"Lucas Santos","path":"/LucasSantos91","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/117400842?s=80&v=4"},"commit":{"message":"Reuse precomputed bounds.\nwhen calling `lowerBound` and `upperBound`, the previous implementation was discarding information about low and high bounds that had already been computed.\nThanks, @Olvilock.","shortMessageHtmlLink":"Reuse precomputed bounds."}},{"before":null,"after":"0df1d78d78f21ba27c4f35e02d26deb5af1af4d0","ref":"refs/heads/equalRange","pushedAt":"2024-09-03T02:14:54.000Z","pushType":"branch_creation","commitsCount":0,"pusher":{"login":"LucasSantos91","name":"Lucas Santos","path":"/LucasSantos91","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/117400842?s=80&v=4"},"commit":{"message":"`std.equalRange`: Compute lower and upper bounds\nsimultaneously.\nThe current implementation of `equalRange` just\ncalls `lowerRange` and `upperRange`, but a lot of\nthe work done by these two functions can be shared.\nSpecifically, each iteration gives information\nabout whether the lower bound or the upper bound\ncan be tightened. This leads to fewer iterations\nand, since there is one comparison per iteration,\nfewer comparisons.\nImplementation adapted from [GCC](https://github.com/gcc-mirror/gcc/blob/519ec1cfe9d2c6a1d06709c52cb103508d2c42a7/libstdc%2B%2B-v3/include/bits/stl_algo.h#L2063)\nThis sample demonstrates the difference between\nthe current implementation and mine:\n\n```zig\nfn S(comptime T: type) type {\n    return struct {\n        needle: T,\n        count: *usize,\n\n        pub fn order(context: @This(), item: T) std.math.Order {\n            context.count.* += 1;\n            return std.math.order(item, context.needle);\n        }\n        pub fn orderLength(context: @This(), item: []const u8) std.math.Order {\n            context.count.* += 1;\n            return std.math.order(item.len, context.needle);\n        }\n    };\n}\npub fn main() !void {\n    var count: usize = 0;\n\n    try std.testing.expectEqual(.{ 0, 0 }, equalRange(i32, &[_]i32{}, S(i32){ .needle = 0, .count = &count }, S(i32).order));\n    try std.testing.expectEqual(.{ 0, 0 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 0, .count = &count }, S(i32).order));\n    try std.testing.expectEqual(.{ 0, 1 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 2, .count = &count }, S(i32).order));\n    try std.testing.expectEqual(.{ 2, 2 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 5, .count = &count }, S(i32).order));\n    try std.testing.expectEqual(.{ 2, 3 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 8, .count = &count }, S(i32).order));\n    try std.testing.expectEqual(.{ 5, 6 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 64, .count = &count }, S(i32).order));\n    try std.testing.expectEqual(.{ 6, 6 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 100, .count = &count }, S(i32).order));\n    try std.testing.expectEqual(.{ 2, 6 }, equalRange(i32, &[_]i32{ 2, 4, 8, 8, 8, 8, 15, 22 }, S(i32){ .needle = 8, .count = &count }, S(i32).order));\n    try std.testing.expectEqual(.{ 2, 2 }, equalRange(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, S(u32){ .needle = 5, .count = &count }, S(u32).order));\n    try std.testing.expectEqual(.{ 1, 1 }, equalRange(f32, &[_]f32{ -54.2, -26.7, 0.0, 56.55, 100.1, 322.0 }, S(f32){ .needle = -33.4, .count = &count }, S(f32).order));\n    try std.testing.expectEqual(.{ 3, 5 }, equalRange(\n        []const u8,\n        &[_][]const u8{ \"Mars\", \"Venus\", \"Earth\", \"Saturn\", \"Uranus\", \"Mercury\", \"Jupiter\", \"Neptune\" },\n        S(usize){ .needle = 6, .count = &count },\n        S(usize).orderLength,\n    ));\n\n    std.debug.print(\"Count: {}\\n\", .{count});\n}\n```\nFor each comparison, we bump the count. With the\ncurrent implementation, we get 57 comparisons.\nWith mine, we get 43.\n\nThis optimization is orthogonal to left-bias\nproposed by [21278](https://github.com/ziglang/zig/pull/21278)","shortMessageHtmlLink":"<code>std.equalRange</code>: Compute lower and upper bounds"}},{"before":"a673296ab615644251353735cf2b3c08ad7c0a21","after":"bb7baa6fb09d4ded8d79874693f8f125f9a6bb26","ref":"refs/heads/master","pushedAt":"2024-09-02T23:28:46.000Z","pushType":"push","commitsCount":1,"pusher":{"login":"LucasSantos91","name":"Lucas Santos","path":"/LucasSantos91","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/117400842?s=80&v=4"},"commit":{"message":"Fix tests.\nThe tests for the BufferedReader wrongfully expected read to behave like readAll. That is, they didn't expect partial reads.","shortMessageHtmlLink":"Fix tests."}},{"before":"be8a7a0f199761bc31d55dfae538229b5f286882","after":"a673296ab615644251353735cf2b3c08ad7c0a21","ref":"refs/heads/master","pushedAt":"2024-09-02T22:02:29.000Z","pushType":"push","commitsCount":1,"pusher":{"login":"LucasSantos91","name":"Lucas Santos","path":"/LucasSantos91","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/117400842?s=80&v=4"},"commit":{"message":"Simplified implementation.","shortMessageHtmlLink":"Simplified implementation."}},{"before":"5723fcaac1b473acee2fb3f5ea5486527eac5359","after":"be8a7a0f199761bc31d55dfae538229b5f286882","ref":"refs/heads/master","pushedAt":"2024-08-30T18:53:47.000Z","pushType":"push","commitsCount":1,"pusher":{"login":"LucasSantos91","name":"Lucas Santos","path":"/LucasSantos91","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/117400842?s=80&v=4"},"commit":{"message":"Improve efficiency of buffered_reader.\nThe current implementation of buffered_reader always reads from the\nunbuffered reader into the internal buffer, and then dumps the data onto\nthe destination. This is inefficient, as sometimes it's possible to read\ndirectly into the destination. The current strategy generates more\nmemory copies and unbuffered reads than necessary.\nThis PR implements a 3-step algorithm to buffered_reader to resolve\nthese problems.","shortMessageHtmlLink":"Improve efficiency of buffered_reader."}}],"hasNextPage":false,"hasPreviousPage":false,"activityType":"all","actor":null,"timePeriod":"all","sort":"DESC","perPage":30,"cursor":"Y3Vyc29yOnYyOpK7MjAyNC0wOS0yMFQyMjo1MDowMy4wMDAwMDBazwAAAAS8bFVw","startCursor":"Y3Vyc29yOnYyOpK7MjAyNC0wOS0yMFQyMjo1MDowMy4wMDAwMDBazwAAAAS8bFVw","endCursor":"Y3Vyc29yOnYyOpK7MjAyNC0wOC0zMFQxODo1Mzo0Ny4wMDAwMDBazwAAAASo9eYW"}},"title":"Activity · LucasSantos91/buffered_reader"}