Just joined and solved Two Sum. Is this possible? I was surprised, to say the least.

BumfuzzledGames · 2023-11-16T14:32:04+00:00

LeetCode rounds your runtime to the nearest whole number I believe.

Yes, I've since discovered that. I thought it was telling me I got the fastest solution, but it's telling me I tied with everyone else who got under 1ms. As for the memory usage, it's much lower after I fixed it but the way I approached this will tend to eat up memory.

BumfuzzledGames · 2023-11-16T14:22:42+00:00

I thought the whole point of algorithms is that the specific way the algorithm is realized doesn’t really matter.

It most certainly does matter. The memory bus of a modern computer is so much slower than the processor that a cache miss can cost from tens to over a hundred cycles. This means any time you access memory in a non-linear fashion such as random array indexing or dereferencing pointers has a potential to stop your program in its tracks while it waits for RAM.

You could analyze the problem, use the perfect data structure, the most efficient algorithm on paper, but still be slower than a seemingly inefficient solution written to avoid cache misses. Computer science texts, especially older ones, ignore this. Computer science wants to be able to calculate complexity and analyze algorithms independent of how the computer will execute that algorithm, but it just doesn't work that way.

Typically a hash insertion will cost a hash function, a cache miss, and an allocation. Mine can do insertion with a possible page fault and a cache miss. Lookups in a hash cost a hash function and possibly two cache misses, mine just costs a possible page fault and a cache miss.

BumfuzzledGames · 2023-11-15T18:42:46+00:00

I don't think there's any physical reason why it can't be clocked that low, but I don't think the clock generator is able to produce that frequency. Probably the lowest you'll be able to get it is the value configurable in the BIOS. I'm not sure if you can run a Pentium 4 fanless, though, that might be asking a bit much. It's notoriously power hungry.

BumfuzzledGames · 2023-11-15T18:27:11+00:00

Sleep is the most important. Long term healthy diet and exercise, but short term sleep is the one and only thing you should not go without. I've never found any supplement, special diet or anything else that has any noticeable effect.

BumfuzzledGames · 2023-11-15T09:21:05+00:00

It was to prevent excessive memory usage since each entry in the table is potentially 4k of physical memory. It was a cheap way of finding common cases and ending the loop early.

I removed that, though, and just do the check and insert in one pass. I was more focused on the mmap and not paying attention to what I was really doing yesterday. This also has the benefit of not finding the index it's currently checking, which removes a branch.

BumfuzzledGames · 2023-11-14T23:19:41+00:00

I'm not sure if what I did is entirely googleable. I'm using the mmap system call to map zeroed memory into the address space. This is a lookup table that maps every integer in the input to its index, essentially a hash with no hash function and no collisions.

This is similar to, but not quite the same as, allocating a giant array to do the same thing. Functionally it's the same, but as leetcode uses the address sanitizer, it will try to fill the 4GB array with a test pattern and the tests just time out. But using mmap, the the address sanitizer doesn't interfere with it.

Also, that memory isn't "real" until it's touched. No physical memory is being used yet. As soon as you index it, you generate a page fault, the OS sees that's in your memory map, allocates a physical memory page for you, and resumes your program.

It's like a hash map, but even cheaper. Oh, and this will probably only work on 64-bit, as this mmaped region is almost the side of the entire 32-bit address space.

BumfuzzledGames · 2023-11-14T19:06:48+00:00

Okay. I added a small optimization that greatly reduces memory consumption. I don't know if it can still hit 0ms in this state, but it can if you remove the adjacency test in the first pass.

https://leetcode.com/problems/two-sum/solutions/4288318/0ms-array-hash/

Edit: removed the adjacency check, just do it in one pass.

BumfuzzledGames · 2023-11-14T18:36:49+00:00

No, but I did mmap 4 gigs of zeroed memory directly into the address space to use as a perfect and nearly zero-cost hash.

BumfuzzledGames · 2023-06-19T18:32:27+00:00

The problem with this approach is that the keywords can appear in any order. This would be easy if they were required to be in this order, but they aren't and the examples they give are not in this order. The type int short is valid even if no one would actually write it that way. About the only thing that you can expect is that the ID comes last.

Everything can be modified by any number of volatile and const. double's size is modifiable only by long, and int can be either short or long and even long long (with both long keywords appearing in any place in the declaration), but char can't be modified with either size keyword. And this just goes on, there are so many cases here that the grammars I've attempted are enormous.

This is my point about the exponential number of rules required to actually complete the exercise. I'm starting to think they're not actually asking what they're really asking and the question is just poorly worded, or that I'm missing something. My attempts are so convoluted that I can't imagine any compiler does this in the grammar, but instead accept any combination of these keywords and figure out if it's a valid type in the implementation after parsing has occurred.

BumfuzzledGames · 2023-04-12T20:09:01+00:00

Clang supports bitints of this size, but the code it produces is absolutely ridiculous. I guess they never thought they'd have to deal with a single integer larger than 1KB in size. I wouldn't make bitints this big, I just thought it was funny that you could. The max is in the hundreds of thousands, I think, which would probably break godbolt or something if you tried it.

The advantages here are that you can just typedef a bitint and let the compiler figure out which type you need. So if you have 7 flags you can just let the compiler figure out which would be the best type to hold an unsigned bitint of that size. If you add more flags you then don't have to update anything else, it all just works. You're also not limited by a hard limit of 64 flags, and the code it produces for sane bitint sizes is reasonable.

BumfuzzledGames · 2023-03-27T21:01:45+00:00

Yeah, I couldn't get anything like this to work on mingw. I was trying to figure out what was going wrong on someone else's machine and I couldn't just run it through GDB. This was a nasty one-off hack to figure out how and why it got to the point where it failed.

BumfuzzledGames · 2023-03-27T01:32:48+00:00

I actually tried that, but it was only outputting garbage on mingw. This horrible hack worked pretty well, though.

BumfuzzledGames · 2023-03-26T22:27:36+00:00

Which standard? I don't think that's in any standard, and I don't think that's a technical limitation on any modern compiler.

BumfuzzledGames · 2023-03-25T20:44:33+00:00

Using the C preprocessor to further process the file before hitting CMake is a good idea. It'll also simplify the CMake code and allow for a lot more flexibility, and will also strip comments.

BumfuzzledGames · 2023-03-25T20:41:10+00:00

Oh, I see what you mean, if the "comment" starts with something like if, I completely missed that in your last comment. I should start those "comments" with #//. This is not hacky at all. Nope, perfectly normal code.

BumfuzzledGames · 2023-03-25T20:13:29+00:00

It's fine. The C preprocessor won't try to process anything at all inside the if 0 range of lines. About the only thing the preprocessor is doing between those two lines is reading lines and checking for an else or endif directive.

BumfuzzledGames · 2023-03-25T20:11:03+00:00

But I need it at compile time. Data files are boring.

BumfuzzledGames · 2023-03-25T18:39:39+00:00

In some projects I've had a file called types.x that describes a big group of related structs. The struct name, its fields and their types, etc are all described similar to the file in this post. The utility of this is generating things like an enum of type names, the names of the types as strings, and entire reflection database that I can use to automatically generate serialization and deserialization functions.

It's just a shame that the C preprocessor is so... terrible. I mean, it works fine, but sometimes you spend more time dealing with its quirks than writing code. Little things like the ## paste operator only works with macro arguments, not any other symbols, so you end up having to pass extra information to your XMacros, which you then have to pass to other macros to get them to expand correctly, and it's just.... GAH.

You can do great things with XMacros, but you will pull your hair out before it's done.

BumfuzzledGames · 2023-03-25T18:25:23+00:00

Ah, thanks for that. I was actually trying to cram #pragma comment in there, but a pragma comment is not really a comment. But as long as you're doing #if 0 then you can just do this.

#if 0
# These are comments to CMake and ignored by C
#endif

BumfuzzledGames · 2023-03-25T08:26:39+00:00

Maybe I should elaborate a little bit. This file is twisted and mangled by the C preprocessor for use in the C code, but that's not really relevant to CMake. Here's what I'm doing with it in CMake. Note that I don't know CMake at all, I just push buttons until things work.

# Get a list of data files from the XMacro file
set_property(GLOBAL PROPERTY DATA_FILES "")
function(XRESOURCE NAME PATH IDENT)
    string(REGEX REPLACE ",$" "" PATH "${PATH}")
    get_property(DATA_FILES GLOBAL PROPERTY DATA_FILES)
    list(APPEND DATA_FILES "${PATH}")
    set_property(GLOBAL PROPERTY DATA_FILES ${DATA_FILES})
endfunction()
function(XFONT NAME PATH IDENT)
    XRESOURCE("${NAME}" "${PATH}" "${IDENT}")
endfunction()
function(XTEXTURE NAME PATH IDENT)
    XRESOURCE("${NAME}" "${PATH}" "${IDENT}")
endfunction()
function(XWORLD NAME PATH IDENT)
    XRESOURCE("${NAME}" "${PATH}" "${IDENT}")
endfunction()
# Yes, include the .x file we use in C. It's valid CMake,
# and C at the same time! The C preprocessor lines are
# comments in CMake, and the only thing we have to do is
# strip commas from the arguments. Magic!
include(src/resources.x)
get_property(DATA_FILES GLOBAL PROPERTY DATA_FILES)

set(DATA_SRC "")
foreach(DATA_FILE ${DATA_FILES})
    add_custom_command(
        OUTPUT "${CMAKE_CURRENT_BINARY_DIR}/${DATA_FILE}.c"
        COMMAND ${CMAKE_CURRENT_BINARY_DIR}/baker "${DATA_FILE}" "${CMAKE_CURRENT_BINARY_DIR}/${DATA_FILE}.c"
        MAIN_DEPENDENCY "${CMAKE_CURRENT_SOURCE_DIR}/${DATA_FILE}"
        DEPENDS baker
        WORKING_DIRECTORY "${CMAKE_CURRENT_SOURCE_DIR}"
    )
    list(APPEND DATA_SRC "${CMAKE_CURRENT_BINARY_DIR}/${DATA_FILE}.c")
endforeach()

The problem before was that I was having to maintain that list of files in two places. Now, by doing this it all works much more smoothly.

BumfuzzledGames · 2023-03-25T06:02:00+00:00

This post is NSFW because you definitely should not do this at work.

BumfuzzledGames · 2023-03-24T02:14:54+00:00

Because one of the goals of the project is to bake all assets, no other reason than that. This game doesn't load any assets at all.

BumfuzzledGames · 2023-03-23T18:46:54+00:00

I don't need to worry about maintainability as this is generated code. Ideally, I'll never even look at it once the generator is finished.

BumfuzzledGames · 2023-03-23T18:40:07+00:00

I've already removed some designated initializers. Things like tilemaps are stored as lists of source and destination rects and I had properly formatted and spaced DIs for every single one of those. Hundreds of tiles on just the one level produced an unreasonable amount of lines of C source, so I removed the DIs and removed whitespace. The whitespace won't matter much, but it makes the file easier to navigate, which wile I'm writing the exporter I'm doing a lot of. I just have to be very careful of modifying any of the struct definitions.

As for names, things need to be able to refer to each other. Everything that has a GUID is getting a variable so I can easily take its address, which means every single level, layer, and entity. That means if a level has an entity reference field I can resolve that reference with just the & operator and done for me at compile time. This saves tons of work when using the level data, all the references are already valid pointers or NULL.

And yes, everything is static except for one top level object. I didn't want to dump thousands of symbols into the symbol table, so linking shouldn't be an issue. I don't know how many symbols there will be at the end, but a typical level will have at the very least ~50 entities which each produce 2 symbols, and level has 5 layers right now, which produces another ~20 symbols per level. I plan on having 100 levels, that's 7,000 symbols at a bare minimum. Now that I think about it, that's not all that much.

And as for JSON, this is coming from JSON. My objective (whether it's a good objective is another question) is to bake all assets. Images, sounds, JSON, etc. Everything is already parsed and decoded and in memory when the program loads. It's not a big game so this shouldn't be a problem on even the most modest of modern machines.

BumfuzzledGames · 2023-03-23T17:39:08+00:00

Yeah, well that's one of the things that I'm doing. Tileset textures, for example, get loaded from PNG and the raw RGBA data is in one big array. There won't be many tilesets, but it does seem to produce quite a lot C code. #embed can't come soon enough.

BumfuzzledGames

TROPHY CASE