Strange Container

[aklepatc]

Code a data structure with 2 operations: push() and popMostFrequent().

Most of the meat is in the comments/discussion below.

Comments

[aklepatc]

Most frequently "encountered" in the container...

Say, 42 was pushed 7 times (not necessarily in sequence). It became the most frequent element. Then it was popped twice. Count/frequency went down. And now it is no longer the most frequent element.

[sassa_nf]

https://tio.run/##fVI9b4MwFNz9K05MdktRskalWzslUnbEQIlJIWAsYpCiKr@dPttAi9R24@593Lsz53YcdZZfsrNEk5WKsbLRbWfAGRAUjQmYYMzctMRbr9QNV9P1ucEnlQ80oRMiSnVOS2WI2iNJk9RT7M5Y0ascPMeDGxY49tcPPsA3CLelLJBHB8QxVFk7Bp6g7RfJ1xKCyrQWqLCLbVsypAzTB41Uj1u/ssJLjFoqnkd7sWzdU0umtVQny4dW0W90xaRKV3XCIQbxq49WcwHuDwshu67tvIw7bBF@wnLPMzbTHZ00facQBCEo4OjVDhc80K2GbLS5BYvLIeswp2Vh@H2m/0g26cwl213qtSZ14oSNdbOybwu7Kp0V3Gk/mk6ylkbS@MFZpy7I@iq/32XKeXLmdkx@Bpfnkpb9m7jPxNtw0VkUub8gyJzPGb2vUPYPsp0EbXRHCsbUilPJPoj4i76P4xc

[aklepatc]

Perfect! That's what they wanted to see.

One nit though: you are popping the least recently pushed most frequent element...

It makes a tiny bit more sense to pop the most recently pushed one (the last element of the same slice). More sense from both semantical and performance POV.

[sassa_nf]

It was a bit more to type on the phone. :)

Performance-wise - ... it's a slice, they do not necessarily move the data. I don't know what they do, but I wouldn't assume.

[aklepatc]

The way you doing it is "loosing" 2 machine words of memory (size of string). If you popped from the end of the slice instead then those 2 words would be reused the next time you append().

Go string is a pointer + length on the inside AFAIU. Hence 2 words.

[sassa_nf]

https://tio.run/##NYu9DoMgFIX3@xQnThAd6NDF1icxDrcIFA1ItJ0an51iU89yfr4ct@ScWM/sDAL7SGTfUf@ikPgQgIC2K8NsRD9sr9VH10DJg9hlxXRQdSt@x1X9VWpdn@8OnJKJowgNKn7o0Vj39FMlTxz6SzvQTnvOXw

So this leaks 5GB or what? I am not sure how this works in go

[aklepatc]

This memory is not completely lost for the lifetime of the process. It is freed/reclaimed every time the slice gets reallocated by append().

So it is only "leaked" until the next append() causes reallocation. "Normally" though, append() does not cause reallocation. So you don't know for sure when (if ever) the memory is returned to the process.

You keep truncating the buffer on the left... So you might be causing reallocation on every loop iteration? I'm not too sure TBH.

Language standard does not (precisely) specify reallocation policy. AFAIU in practice reallocation doubles capacity. But I am not too sure what the base number is: original capacity or original length. So I cannot confidently reason about how many reallocations your code would cause.

[aklepatc]

A bit off topic...

The way you doing it in your last example is the naive way people implement FIFO queue (in both Go and Python). It works but is suboptimal b/c the memory for the popped elements is not reclaimed until reallocation.

A better way to do FIFO is a ring buffer like structure.

[sassa_nf]

Yes, almost. The difference really isn't the memory retention, but when reallocation happens and what the footprint requirement is.

I.e if you pop from the back, you retain just as much memory as when you pop from the front. The difference is that if you pop from the front, this will trim to size upon the next push, but if you pop from the back, you will retain the historically biggest array.

But we can't really tell how that works, because it is a slice, an abstraction. So it may well be a ring buffer underneath, why not?

Of course, the experiment shows that the implementation isn't a ring buffer:

https://tio.run/##bY7NCsIwEITv@xTLnhIoUvFW6Dt4Lz3E/qXUbENNQSM@e4ypCIqngfm@gRnmEKxqJjV0aNTIAKOx8@IEUm8coQToV24SExLvgIgGizIWUyeq@uKWkYcM8wwPcoMlKms7boXJkNpZUwx1aihhTttqX9R/5OvNv60qryMi7z1tq4/H0dNaf3tudQSvIn7eHeMjd2Zh5G/DEh4hPAE

Append behaviour was surprising, though. I.e. that appending to n modified m.

[aklepatc]

I think it's 100% by the spec and not surprising at all.

In Go re-slicing works against the original buffer. This design choice is well understood and documented but it is not the only one possible. In Python re-slicing makes a (shallow) copy of the relevant chunk of the buffer. So unlike Go the original and the new slice are reasonably well decoupled.

I am guessing... If this Go behavior is surprising to you then maybe some of my previous comments wouldn't be quite clear or even would not make much sense?

[sassa_nf]

Well, it is surprising to those familiar with java byte buffers. Slicing a buffer there creates a slice of the underlying buffer, but does not share its limit - can't go beyond the last byte available in the buffer at the time of slicing, even if the capacity allows for that.

So to speak, cap(n)==len(n) immediately after slicing.

[aklepatc]

Interesting. Lots of ways to slice it. Lol.

Go ways are very similar to C ways. So old C ppl find Go easy. In particular, Go slicing resembles C pointer arithmetic when it's used say to move a window over a larger array.

[aklepatc]

I believe, the only thing not precisely specified is how much extra capacity gets allocated if append() must cause reallocation.

In particular, Go slice is definitely not a ring buffer.

[aklepatc]

Another nit.

I am afraid this:
v, c.L[j] = c.L[j][0], c.L[j][1:]
is a memory leak (sorta). It would not be an issue if the slice elements were say int or float though.

Two ways to loose memory here:
1. String can "never" be GC-ed. This is the worst one.
2. Zero-th element of the slice is lost until the slice is fully reallocated. I _think_ you cannot just re-slice to reclaim/reuse this memory.

The right way to do what you wanted is this:
v, c.L[j], c.L[j][0] = c.L[j][0], c.L[j][1:], nil

[sassa_nf]

Good point about clearing the reference. But the order may matter.

Eg

v, c.L[j], c.L[j][0] = c.L[j][0], c.L[j][1:], nil

c.L[j][0] on the left - does that refer to the c.L[j] before or after assignment of c.L[j][1:] to it?

[aklepatc]

AFAIU the order doesn't matter.

These assignments work like they do in SQL update. Everything to the left of "=" is "after" the change and everything to the right is "before".

If course, I could write a quick test and/or even dig up a link to the relevant place in the spec. Please forgive me for being too lazy.