[bug]: Chip part order still matters

[netalondon]

Tool

Hardware Simulator

Interface

Website (https://nand2tetris.github.io/web-ide)

Contact Details

No response

What happened?

This implementation of the computer chip passes ComputerAdd.tst:

ROM32K(address=pc, out=instruction);
Memory(in=data, load=write, address=address, out=previousMout);
CPU(instruction=instruction, inM=previousMout, reset=reset, outM=data, writeM=write, addressM=address, pc=pc);

While this one fails:

ROM32K(address=pc, out=instruction);
CPU(instruction=instruction, inM=previousMout, reset=reset, outM=data, writeM=write, addressM=address, pc=pc);
Memory(in=data, load=write, address=address, out=previousMout);

(Only difference is switching the order of the last 2 lines)

Additional Comments

No response

Do you want to try to fix this bug?

• [ ] I want to try to add this feature!

Code of Conduct

• [X] I agree to follow this project's Code of Conduct

[netalondon]

@DavidSouther I'm digging into the Java simulator code and can't seem to understand how it determines the order in this case.

Could you take a look at this when you have time?

[DavidSouther]

Here's my notes:

CompositeGateClass.java

Tracks connections.

ConnectionSet is a HashSet, so iterator has no defined order.

Insertion via CompositeGateClass -> readParts -> readPinName -> addConnection -> connections.add

Then later to sort, it iterates connections, then adds edges to the graph. Graph edges are another HashMap, so no order guaranteed.

There is no guaranteed sort order, so the naive topological sort is going to depend on the JVM's implementation of HashMap. There are a number of algorithms to cut graphs, and the reality is that the Java implementation is "random, but probably the linear in the hash of the memory address of the object modulo the current size of the backing array" (I don't see any overrides of hashCode()).

In Javascript, the order is guaranteed to be insertion order, so changing the order of lines in the source will always change the order of connections (and thus, which connection is cut) when stable sorting in the web implementation.

[netalondon]

@Davidsouther apparently this isn't a sorting issue but a side effect of #344. (If we merge in #381 both cases fail, and reverting #344 fixes that).

In changing the CPU emulator we also changed the builtin CPU chip.

How do you think we should handle this? Should I separate the CPU emulator/builtin-chip implementations?

[DavidSouther]

Should I separate the CPU emulator/builtin-chip implementations?

It bothers me aesthetically to make them different, but I can't point out a reason why they shouldn't otherwise be their own pieces of code. It seems like they should be able to be, but maybe the spec doesn't quite fit?

[netalondon]

apparently this isn't a sorting issue but a side effect of https://github.com/nand2tetris/web-ide/pull/344. (If we merge in https://github.com/nand2tetris/web-ide/pull/381 both cases fail, and reverting https://github.com/nand2tetris/web-ide/pull/344 fixes that).

@DavidSouther this was wrong, sorry about that! After checking again it looks like #344 has no effect here, I'm not sure why I thought it did.

To complicate things further, #381 doesn't fix the sorting here (only in #360).

I see that the Java version references 'clocked pins' as opposed to 'clocked chips' here for example. Here is my attempt at replicating this, but it still doesn't fix the issue.

I'll continue looking into it, let me know if you have any insights.