Home/Data Structures & Algorithms/Bit Manipulation & Low-Level Computing
  1. Asked: September 11, 2026In:

    PyTorch RuntimeError: CUDA out of memory: Why torch.cuda.empty_cache() fails & how to fix fragmentation

    Anonymous
    Anonymous Begginer

    Direct Technical Solution: torch.cuda.empty_cache() releases only cached (unallocated) blocks back to the CUDA driver; it never frees memory occupied by active tensors (weights, optimizer states, computation graph nodes). Calling it inside your training loop hurts performance because CUDA must constRead more

    Direct Technical Solution: torch.cuda.empty_cache() releases only cached (unallocated) blocks back to the CUDA driver; it never frees memory occupied by active tensors (weights, optimizer states, computation graph nodes). Calling it inside your training loop hurts performance because CUDA must constantly re-allocate OS memory via costly system calls.

    1. Root Cause: PyTorch Allocator Memory Fragmentation

    Look closely at your error message: 18.21 GiB allocated + 4.80 GiB reserved. PyTorch had nearly 5 GB of memory held in its internal caching allocator, but it was split into scattered, non-contiguous memory chunks. When a tensor required 512 MiB of contiguous VRAM, the allocator failed to find a single chunk large enough.

    2. The Modern Fix: Expandable Segments (PyTorch 2.0+)

    The definitive solution in modern PyTorch is activating virtual memory management via the expandable_segments flag. This instructs CUDA to map physical memory pages to a contiguous virtual memory space, virtually eliminating memory fragmentation:

    # Terminal / Docker Entrypoint (Set before launching Python)
export PYTORCH_CUDA_ALLOC_CONF=expandable_segments:True

# Or directly in Python before calling any CUDA operations:
import os
os.environ["PYTORCH_CUDA_ALLOC_CONF"] = "expandable_segments:True"
import torch

    3. The 4 Golden Rules to Prevent CUDA OOM

    • Detach Loss Values: Never accumulate raw tensor losses: total_loss += loss retains the entire backward computation graph in VRAM! Always use total_loss += loss.item().
    • Use Automatic Mixed Precision (AMP): Halve activation memory using native BF16/FP16:
      with torch.autocast(device_type="cuda", dtype=torch.bfloat16):
    outputs = model(inputs)
    loss = criterion(outputs, targets)
    • Gradient Accumulation: Instead of a batch size of 64 that OOMs, use a micro-batch size of 16 and accumulate gradients across 4 backward steps:
      loss = loss / 4
loss.backward()
if (step + 1) % 4 == 0:
    optimizer.step()
    optimizer.zero_grad(set_to_none=True)
    • Zero Gradients with `set_to_none=True`: optimizer.zero_grad(set_to_none=True) deallocates memory instead of zeroing tensors with zeros of equal size.
    See less
    • 0
  2. Asked: September 11, 2026In: ,

    How to find the Single Number when all others appear 3 times using a Digital Logic State Machine?

    Abhay Tiwari
    Abhay Tiwari Begginer

    This problem is a masterpiece of digital circuit design translated into software code. Let's design the state machine from first principles. 1. The Three States of a Bit For any bit position, as we scan numbers in the array, how many times can we see a 1? Seen 0 times → Count = 0 Seen 1 timeRead more

    This problem is a masterpiece of digital circuit design translated into software code. Let’s design the state machine from first principles.

    1. The Three States of a Bit

    For any bit position, as we scan numbers in the array, how many times can we see a 1?

    • Seen 0 times → Count = 0
    • Seen 1 time → Count = 1
    • Seen 2 times → Count = 2
    • Seen 3 times → Resets back to 0!

    To represent 3 distinct states (0, 1, and 2), we need 2 bits of memory! Let’s name them:

    • twos (the high bit)
    • ones (the low bit)

    2. The Truth Table

    When a new bit x arrives from the current number:

    Current State (twos, ones)Input Bit (x)Next State (twos, ones)Explanation
    0, 000, 0Seen 0 times
    0, 010, 1Seen 1 time
    0, 100, 1Unchanged
    0, 111, 0Seen 2 times
    1, 001, 0Unchanged
    1, 010, 0Seen 3 times → RESETS TO 0!

    3. Deriving the Logic Gates

    From the truth table:

    • ones = (ones ^ x) & (~twos)
    • twos = (twos ^ x) & (~ones)

    When the full array has been scanned:

    • Every element that appeared 3 times completed the full cycle $(0 o 1 o 2 o 0)$ and returned both bits to 0.
    • The single element that appeared 1 time transitioned from $0 o 1$. Its bits are left recorded inside ones!

    Clean Python 3.12 Implementation

    def single_number(nums: list[int]) -> int:
    """Finds element appearing once while others appear 3 times in O(N) time and O(1) space."""
    ones = 0
    twos = 0

    for x in nums:
        # Update ones: XOR with x, but clear if twos already holds this bit
        ones = (ones ^ x) & ~twos
        # Update twos: XOR with x, but clear if ones now holds this bit
        twos = (twos ^ x) & ~ones

    return ones

    Complexity Breakdown

    • Time Complexity: O(N). We touch each number once with 4 single-cycle bitwise operations.
    • Space Complexity: O(1). Exactly two integer variables living in registers.
    See less
    • 0
  3. Asked: September 11, 2026In: ,

    How does Brian Kernighan’s bit algorithm work, and why does n & (n – 1) clear the lowest set bit?

    Abhay Tiwari
    Abhay Tiwari Begginer

    The trick n & (n - 1) is one of the most elegant one-liners in computer engineering. Let's look at the exact bitwise mechanics so the mathematical proof becomes obvious. 1. What happens when you subtract 1 in binary? Think about standard base-10 math: when you subtract 1 from 1000, what happens?Read more

    The trick n & (n - 1) is one of the most elegant one-liners in computer engineering. Let’s look at the exact bitwise mechanics so the mathematical proof becomes obvious.

    1. What happens when you subtract 1 in binary?

    Think about standard base-10 math: when you subtract 1 from 1000, what happens? The lowest non-zero digit (1) becomes 0, and all trailing zeroes become 9s: 0999.

    Binary works exactly the same way, but with 0s and 1s:

    Any positive binary integer can be written in this general form:

    n = (arbitrary prefix) 1 0 0 0 ... 0

    where the 1 shown is the lowest set bit (the rightmost 1), followed by zero or more 0s.

    When you compute n - 1:

    1. The arbitrary prefix before the lowest 1 remains completely untouched.
    2. That lowest 1 turns into a 0 (borrowing from the subtraction).
    3. All the trailing 0s flip into 1s!
        n     = (prefix) 1 0 0 0
  n - 1   = (prefix) 0 1 1 1

    2. The Bitwise AND Operation: n & (n – 1)

    Now perform a bitwise AND between n and n - 1:

        n     = (prefix) 1 0 0 0
& n - 1   = (prefix) 0 1 1 1
----------------------------
  result  = (prefix) 0 0 0 0

    Look at what happened:

    • The prefix matched identically → remains preserved.
    • The rightmost 1 was paired with 0 → becomes 0!
    • The trailing 0s were paired with 1s → remain 0!

    Conclusion: The operation n & (n - 1) turns off the lowest set bit in n and leaves every other bit completely unchanged. Pure mathematical magic!

    3. Real-World Applications

    A. Counting Set Bits in O(k) time (where k is number of 1s)

    Instead of looping 32 or 64 times, Brian Kernighan’s algorithm loops only as many times as there are 1-bits:

    def count_set_bits(n: int) -> int:
    count = 0
    while n > 0:
        n &= (n - 1)  # Strips off one set bit per loop iteration
        count += 1
    return count

    If a 64-bit integer has only two set bits, this loop executes exactly twice and terminates!

    B. Instant Power of Two Check in O(1)

    A power of two in binary has exactly one set bit (e.g. 8 = 1000_2, 16 = 10000_2). If you strip that single bit and the result is 0, it was a power of 2:

    def is_power_of_two(n: int) -> bool:
    return n > 0 and (n & (n - 1)) == 0

    C. Hardware POPCNT Alternative

    On modern x86_64 CPUs, you have the dedicated hardware assembly instruction POPCNT (or __builtin_popcount in GCC/Clang), which computes set bits in a single CPU cycle. But when writing portable code or kernel routines without AVX/SSE guarantees, Brian Kernighan’s algorithm remains the golden standard.

    See less
    • 0