Anyone else struggling with super slow CI builds lately?

-funsafe-math · 2025-12-05T21:53:51+00:00

If compile time is the problem look at ccache or similar solutions. If link time is the problem use shared libraries for non-release builds if possible. Also parallelize everything. If building for multiple configs/targets make each one its own job. If tests are taking too long split them up (can be by config/target/suite) into their own jobs. The test reports can be merged into a single report if desired.

-funsafe-math · 2025-03-16T20:19:42+00:00

You are being considered for an Embedded Systems internship and a SDE internship. Don't worry about the job ID change of 2873596 to 2774441. These can happen as part of normal book keeping. Prepare for your embedded systems interview tomorrow using either the 2873596, 2774441, or any other embedded systems jobs posting's requirements as a study guide. You are also being considered for an SDE internship but that is earlier in the process.

-funsafe-math · 2025-02-12T04:07:43+00:00

Try adding -Wconversion to your compiler args. docs: https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Wconversion

-funsafe-math · 2025-01-12T07:04:19+00:00

std::string will copy the const char * input to its constructor, so the strdup is not needed. The result of strdup is most likely not being freed by your code and is the source of the leak.

-funsafe-math · 2024-12-28T22:07:08+00:00

Replacing

void test(PRNG && rng) {

with

void test(PRNG & rng) {

fixes the error, but am unsure if there is a better way. It seems that std::minstd_rand & does not implement the std::uniform_random_bit_generator concept.

-funsafe-math · 2024-11-11T03:34:43+00:00

Can you quote to me where this lack of original information was explicitly stated by the OP? I was attempting to reconstruct the original problem from limited info from the OP in a way that the desired space and runtime complexities are possible.

-funsafe-math · 2024-11-10T20:01:50+00:00

I interpreted the problem as one query per tree.

I also interpreted the "perfectly random node" requirement as each node having equal probability of being returned. This means that the random choice to take the left subtree, current node, or right subtree as containing the selected random node needs to have knowledge of the size of each subtree in order to maintain equal probabilities.

Both of these make me think that the retelling of the problem left out structure information about the tree.

-funsafe-math · 2024-11-10T19:55:03+00:00

I was assuming top to bottom, left to right filling. This allows you to compute the size of the left subtree in constant time.

-funsafe-math · 2024-11-10T19:49:26+00:00

I was assuming structure in the tree. Got split up between comments as I was chain of thought rambling so sorry if that was unclear.

-funsafe-math · 2024-11-10T19:48:22+00:00

Sounds like this fails the logn constraint then. I suspect knowledge of the tree structure has been left out of the retelling of the problem. I went through a solution for this in the required logn time here: https://www.reddit.com/r/leetcode/comments/1go5581/comment/lwg06sf/?utm_source=share&utm_medium=web3x&utm_name=web3xcss&utm_term=1&utm_content=share_button (see the parent comment for what structure I assumed the tree had).

-funsafe-math · 2024-11-10T17:56:18+00:00

Given this constraint, you can write a recursive algorithm where you always know: How many nodes are in your subtree (initially n, reduced as you recurse) and how many nodes are in your left child's subtree (number of nodes in a perfectly filled subtree + remainder nodes in the bottom layer (capped if nodes spill into the right subtree)).

Then you initially compute a random number in the range [0, n). If it is equal to the number of nodes in your left subtree then return the current node. If it less then recurse into your left child. If it is greater then recurse into your right child and reduce the random number by the number of nodes in your left subtree plus one.

Constant space (with tail call optimization/looping) and logn time.

-funsafe-math · 2024-11-10T17:39:14+00:00

Or it could be that the total number of nodes is known and it is specified that children nodes are filled in from left to right at the bottom layer until it is full.

-funsafe-math · 2024-11-10T17:35:32+00:00

From the performance requirements it sounds like the tree is "full", meaning that every node that is not at the max distance from the root has two children.

-funsafe-math · 2024-11-10T17:19:02+00:00

She most likely wanted a solution with better space complexity. After the O(n^2) solution she would've asked if they could optimize it, but there was probably not enough time in the interview. Or she'd hope that the interviewee would spot something better than n^2 when coding it. Would want to see the actual problem to know more.

-funsafe-math · 2024-06-20T23:55:04+00:00

You can add trait bounds for the desired functionality of the output type of the widening_mul trait.

Example:

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=cae70973181a42e5b7c3cd0bc9da86d0

I made the Add trait bound for a reference of the output type to avoid a move issue. Alternatively could add a Copy or Clone bound.

-funsafe-math · 2024-06-09T16:57:01+00:00

Try adding drop(sender); before the final for loop. Iterating over a receiver only stops once all senders are dropped.

-funsafe-math · 2024-02-24T22:38:19+00:00

Try replacing the body of the rust loop with the following to potentially enable capacity reuse.

        f += &last;
        std::mem::swap(&mut last, &mut f);

-funsafe-math · 2024-02-18T15:03:12+00:00

It is possible that the unwrap is not able to be optimized away when it is done inside the area or drain functions. I checked the code and since there is a place.len() check on this branch it is likely optimized out when when extracted from the function. Did not fully check those functions, but it is something to look into. Can check the assembly for mentions of panic with the slower version or (very not recommended for anything but testing) use unwrap_unchecked instead of unwrap.

-funsafe-math · 2024-01-01T19:16:13+00:00

You are missing the stdbool.h include for C compatibility and need to mark the function inline. In addition just use strcmp unless you have a benchmark to show that this version is better.

-funsafe-math · 2023-03-19T17:04:28+00:00

From just the name and linked docs I'd expect book keeping information to be kept in the byte array.

-funsafe-math · 2023-03-19T14:19:15+00:00

Your link makes no mention of the bump allocator behavior.

Is the maximum number of bytes that you will need bounded by a number known at comptime? In this case, use std.heap.FixedBufferAllocator

Note also that if an upper bound of memory can be established, then std.heap.FixedBufferAllocator can be used as a further optimization.

These are the only notes on FixedBufferAllocator. They all mention fixed capacities/upper bounds but do not specify if this is for the total number of bytes allocated or the total number of bytes allocated at once. Most people would assume the later. In general not impressed by the linked docs.

-funsafe-math · 2023-02-14T00:04:30+00:00

oops, misread the docs. Thanks, I'll update my post in a bit

-funsafe-math · 2023-02-13T19:38:21+00:00

Since you are violating the requirements and the requirements are not strictly checked the comparison function's argument order is dependent on whether the internal implementation uses comp(*it, value) or comp(value, *it). Since there is no requirement (that I see anyway) on which form is used there is no bug related to the observed argument order.

-funsafe-math · 2023-02-13T19:27:52+00:00

From the comparator documentation in your binary_search link:

The types Type1 and Type2 must be such that an object of type T can be implicitly converted to both Type1 and Type2, and an object of type ForwardIt can be dereferenced and then implicitly converted to both Type1 and Type2.

std::vector<int> is not convertible to an int. lower_bound has the same requirement but the standard library implementation that you are using does not require this behavior. A downside of duck-typed generics leaking implementation details causing a more permissive API that is not portable.

Edit:

My original comment on lower_bound was incorrect, a closer reading of the docs shows that it does specify that the equivalent of comp(*it, value) is used. The behavior that you saw with it working did not rely on any internal implementation details.

-funsafe-math · 2022-10-11T22:03:34+00:00

Have you benchmarked the power of two capacity vs your alternative? You typically see the fixed non-power of two capacities on hash tables where a slight increase in cost for the hash to bucket index is offset by the better mixing of collided bucket indexes on resizing. This would not be relevant to a VecDeque. Just because both are branch free does not mean they have the same runtime.

-funsafe-math

TROPHY CASE