Notch's Specification for the In-Game DCPU-16 • Hacker News Board

Re: Notch's Specification for the In-Game DCPU-16

#81

Post by aidenn0 » Wed, Apr 04, 2012, 4:55 PM UTC

keenerd wrote: post #18

unwind wrote: post #2

Just waiting for the first post about programming this CPU to pop up on Stack Overflow ... :) It's quite an interesting architecture. From an initial perusal, I found these features note-worthy: * Explicit access to PC as a register, makes "computed goto" trivial and very natural. * Because of the above, there is no JMP instruction. * Treating operations on registers as "values" makes the instruction set very orthogo…

> No instructions for bit-manipulation. What? Plenty of opcodes for that. SHL, SHR, AND, BOR, XOR are all bitwise operators. Unless you mean bitset and bitclear macros, but no self respecting embedded programmer uses those. I've disagreed with almost everything else Notch has done, but from a simple pedagogical standpoint, he's doing the right thing by leaving those out.

No rlwinm

Re: Notch's Specification for the In-Game DCPU-16

#82

Post by RodgerTheGreat » Wed, Apr 04, 2012, 4:56 PM UTC

nknight wrote: post #31

akavel wrote: post #27

Earlier quoted context omitted.

> a highly dynamic language is unlikely Lua, perhaps? There was an article how to reduce its binary size, for an older version of the language (Lua 4.0): http://www.lua.org/notes/ltn002.html With no reductions, and for x86 assembly, it started at ~64KB, so not very useful here; but after dropping standard libraries and parser , they got to ~24KB. Now however, some further questions arise I'm not sure about: - whether…

Lua is a good place to start! And the VM minus parser is useful, though it may make debugging harder. You simply write out the bytecode and upload that. The VM is only part of the problem, though. I consider the bigger problem to be memory management. A garbage collected language operating reliably in 128KB? I'm deeply skeptical.

Garbage collection isn't necessarily that difficult, especially when you're in a single-threaded (or cooperatively multithreaded) environment and don't have to contend with an OS. Here[1] is a cons-pair system I wrote in Forth which uses tag bits to identify pointers, a mark-and-sweep garbage collector and a free-list style allocator. GC takes linear time with respect to heap size, and allocations are constant time. The allocator itself (not counting all the list utility routines) is about 60 lines long and fairly easy to understand.

[1] https://github.com/JohnEarnest/Mako/blob/master/lib/Algorith...

Re: Notch's Specification for the In-Game DCPU-16

#83

Post by cobbal » Wed, Apr 04, 2012, 4:58 PM UTC

ekosz wrote: post #48

I'm not a low level programmer, but could someone tell me if you could write a LLVM backend for this CPU? If one does that, could it not then work with many programming languages that support LLVM? http://llvm.org/docs/WritingAnLLVMBackend.html

I've never written an LLVM backend, but one difficulty that immediately jumps out at me is the 16-bit architecture.

LLVM specifies types with bitwidths and 32 is most commonly used, meaning a backend would have to either emulate 32 bits, forbid the frontends from generating 32 bits, or silently cast them all down to 16 bits.

Re: Notch's Specification for the In-Game DCPU-16

#84

Post by wccrawford » Wed, Apr 04, 2012, 5:01 PM UTC

kierdavis wrote: post #74

Is there an official assembler for this yet, or shall I roll my own?

No, but there's an emulator!

https://github.com/swetland/dcpu16

(Found on Reddit. I haven't tried it.)

Re: Notch's Specification for the In-Game DCPU-16

#85

Post by msarnoff » Wed, Apr 04, 2012, 5:03 PM UTC

dspillett wrote: post #64

unwind wrote: post #2

Just waiting for the first post about programming this CPU to pop up on Stack Overflow ... :) It's quite an interesting architecture. From an initial perusal, I found these features note-worthy: * Explicit access to PC as a register, makes "computed goto" trivial and very natural. * Because of the above, there is no JMP instruction. * Treating operations on registers as "values" makes the instruction set very orthogo…

The thing that looked odd to me was: >* IFE, IFN, IFG, IFB take 2 cycles, plus the cost of a and b, plus 1 if the test fails* It is a long time since I worked in assembly, but I don't remember comparison functions having different timings depending on results when I were a lad. (FYI, most of the assembler I played with was for 6502s (in the old beebs) with a little for the Z80 family and early x86)

AVR behaves similarly. Branch instructions take 1 cycle if the condition is false, and 2 if the condition is true.

Re: Notch's Specification for the In-Game DCPU-16

#86

Post by stephencanon » Wed, Apr 04, 2012, 5:09 PM UTC

unwind wrote: post #2

Just waiting for the first post about programming this CPU to pop up on Stack Overflow ... :) It's quite an interesting architecture. From an initial perusal, I found these features note-worthy: * Explicit access to PC as a register, makes "computed goto" trivial and very natural. * Because of the above, there is no JMP instruction. * Treating operations on registers as "values" makes the instruction set very orthogo…

Ask and ye shall receive: http://stackoverflow.com/questions/10012522/are-the-i-and-j-...

Re: Notch's Specification for the In-Game DCPU-16

#87

Post by tchock » Wed, Apr 04, 2012, 5:09 PM UTC

acron0 wrote: post #53

I will admit, I used to think Notch was just a regular-joe programmer who had gotten extremely lucky with his strain of adventure game. Now I know I was dead wrong.

I am just in awe. This guy has the guts to imagine shit like this and pull it off.

Re: Notch's Specification for the In-Game DCPU-16

#88

Post by untog » Wed, Apr 04, 2012, 5:11 PM UTC

exch wrote: post #23

phoboslab wrote: post #13

Now here's an interesting bit: "Question: can we trade the programs we create? How will you stop malicious viruses etc?" "yes. And I won't stop viruses, the players will have to do that themselves." ~ https://twitter.com/#!/notch/status/187474819980328962

Nice. With a bit of fiddling one could perhaps invert an enemy's shield polarity. That always seems to work miracles in any sci-fi show.

Reverse the polarity of the neutron flow. Works every time.

Re: Notch's Specification for the In-Game DCPU-16

#89

Post by cpeterso » Wed, Apr 04, 2012, 5:16 PM UTC

TomFrost wrote: post #3

unwind wrote: post #2

Just waiting for the first post about programming this CPU to pop up on Stack Overflow ... :) It's quite an interesting architecture. From an initial perusal, I found these features note-worthy: * Explicit access to PC as a register, makes "computed goto" trivial and very natural. * Because of the above, there is no JMP instruction. * Treating operations on registers as "values" makes the instruction set very orthogo…

> * Word-addressed memory will make string processing interesting to implement. Maybe in space, everyone uses UTF-16. Everyone in Minecraft, too -- almost. The string encoding in Minecraft's protocol spec is UCS-2, just a sneeze away from UTF-16. It seems Notch has a soft-spot for large encodings. It makes sense from a calculation and lookup perspective, but I wonder if the increased bandwidth and storage of 16-bit b…

If the DCPU has only 64KB of RAM, encoding strings using UCS-2 or UTF-16 seems rather wasteful.

Re: Notch's Specification for the In-Game DCPU-16

#90

Post by AnIrishDuck » Wed, Apr 04, 2012, 5:17 PM UTC

dspillett wrote: post #64

unwind wrote: post #2

Just waiting for the first post about programming this CPU to pop up on Stack Overflow ... :) It's quite an interesting architecture. From an initial perusal, I found these features note-worthy: * Explicit access to PC as a register, makes "computed goto" trivial and very natural. * Because of the above, there is no JMP instruction. * Treating operations on registers as "values" makes the instruction set very orthogo…

The thing that looked odd to me was: >* IFE, IFN, IFG, IFB take 2 cycles, plus the cost of a and b, plus 1 if the test fails* It is a long time since I worked in assembly, but I don't remember comparison functions having different timings depending on results when I were a lad. (FYI, most of the assembler I played with was for 6502s (in the old beebs) with a little for the Z80 family and early x86)

Many CPUs with branch prediction carry a penalty of a least one cycle for mispredicted branches as the fetch stage(s) of the pipeline must be invalidated. From wikipedia:

The time that is wasted in case of a branch misprediction is equal to the number of stages in the pipeline from the fetch stage to the execute stage. Modern microprocessors tend to have quite long pipelines so that the misprediction delay is between 10 and 20 clock cycles. The longer the pipeline the higher the need for a good branch predictor.

http://en.wikipedia.org/wiki/Branch_predictor

EDIT: the inclusion of this is somewhat interesting as there's not much of a point in simulating a pipelined processor unless you care about hardware details. My best guess is they're adding this "feature" to make compilation to assembly MORE difficult and increase the advantages of hand-compiled assembly. Branch prediction is a tricky thing to do right in compilers.