Thread-Safe Counter

Problem

Implement a Counter class that many threads increment concurrently. It must expose:

• increment(n: int = 1) -> None: add n to the count.
• get() -> int: return the current count.
• increment_and_get(n: int = 1) -> int: add n and return the new value atomically, so that no two callers ever observe the same returned value if each adds 1.

Guarantees: no increment is ever lost, regardless of how threads interleave, and increment_and_get returns values that are unique and monotonically increasing across all threads when every caller adds 1. The class must not rely on the Python GIL for correctness; explain what would break under a runtime without it (or under a compound operation that the GIL does not make atomic).

Then implement a ShardedCounter that spreads increments across several internal counters to reduce contention, and reads by summing the shards.

• increment must be safe to call from any number of threads.
• get may return a slightly stale value for the sharded version but must never return a value that was not a real prefix of the increments.
• No busy-waiting.

Examples

• 8 threads each call increment() 10,000 times → get() returns exactly 80,000.
• 4 threads each call increment_and_get() 1,000 times → the 4,000 returned values are exactly the integers 1 through 4,000, each appearing once.
• ShardedCounter(shards=16) with the same 80,000 increments → get() returns 80,000 after all threads join.

Hints

1. count += 1 is three operations, not one: read the current value, add, write it back. What happens if a second thread does the same three steps in between yours?
2. A mutual-exclusion lock around the whole read-modify-write makes the three steps indivisible from the point of view of other threads.
3. Contention on one lock serializes every thread. If reads are rare and increments are hot, give each thread (or hash bucket) its own lock and sum on read.