4 ms·

That is not a fair comparison at all. 1. An x86 emulator doesn't need to allocate much. It's probably an interpreter. It can parse x86 instructions straight fr

That is not a fair comparison at all. 1. An x86 emulator doesn't need to allocate much. It's probably an interpreter. It can parse x86 instructions straight from a byte vector, and use another byte vector for the RAM. 2. V8 and Firefox have much better garbage collectors than D, because they need their GC to be fast, and so they've made sure it is. 3. Higgs is a much more complex piece of software than this. 4. The 4 seconds time, as I pointed out, is at least 75% GC (but possiby more). That's the whole point of the blog post. It shouldn't be possible for the GC to take most of the execution time.

acqq 12y ago
How many allocations do you actually make to compile a single variable used 60000 times? I still claim you don't have to allocate much too for that particular input, as long as you use vectors/arrays, the ones you also recognize Bellard probably uses and which I've mentioned in my top comment as the right way to make your code faster. It's really as simple as that.
- bmm6o 12y ago
  Read the article, please. My implementation of a liveness analysis scales poorly with function size. It allocates a huge bit matrix (vector of bit sets) for liveness computation. This grows quadratically with the function size, which means that in some cases, obscene amounts of memory are required, and this data structure doesn’t fit in the cache
  - acqq 12y ago
    The "doesn't fit in the cache" argument has nothing to do with too many small allocations which obviously happen (otherwise GC effects wouldn't be noticeable) and which almost certainly can be replaced with much less allocations of some arrays of things. Which it what I suggest since my top comment.
    - tachyonbeam 12y ago
      From the thread on r/programming: "The main issue from the post is quite simple: if you allocate a lot of small objects, D runtime will place them inside chunks (called pools) of fixed size (like 4 MB) that it requested from the OS. Each time a pool is filled up it will do a GC cycle and only if there's still no room for new object it will allocate a new pool. That means number of GC cycles in this situation is proportional to number of objects you allocate, while each GC cycle time is proportional to the managed heap size. It leads to quadratic complexity and awful slowness. If runtime allocated pools not of fixed size but adapted their size to the allocation rate, this scenario could be significantly faster."
- tachyonbeam 12y ago
  This isn't C, it's JavaScript. The semantics of a global variable read are a more complicated than you think. Global variables reside on the global object, which can grow dynamically. Global properties can also be deleted at any time. Accessing a property which doesn't exist should throw an exception. Properties could also be getter functions, which would then result in a function call for every property read. Have you written a JS compiler? Have you written a JIT compiler? Any kind of compiler for a real-world language? A garbage collector? If someone knows of a way to get allocation statistics, then I can answer the question of how many allocations occur.
  - acqq 12y ago
    > Global variables reside on the global object, which can grow dynamically. But it the example you give there's only one single variable. > Global properties can also be deleted at any time. Also doesn't happen in your example. > Accessing a property which doesn't exist should throw an exception. I agree. > Properties could also be getter functions, which would then result in a function call for every property read. But they aren't in your example. And all these aspects result in proportional increase in the resulting code, not in some unexpected complexity. > If someone knows of a way to get allocation statistics Run a Perl script (or Python script or do it by hand) that adds an increment of global nAllocations variable in front of any statement where you do a "new" of something. (If the most of the allocations are implicit, this counting maybe has to be added to the runtime of D, if it already doesn't exist. At least the runtime is open source, AFAIK). Run the program. Print that number. My guess is that it must be an order of 6 digits (millions) for the performance you measure. Which doesn't seem to be necessary to process 60000 evaluations of a single variable if more arrays of fixed sized things could be used in the process. I know for you it's "doctor, it hurts me when I press me here" "well don't do that" moment, but really, that's how it is. A lot of small objects allocated separately makes a lot of work for a GC and it's so in every language. The question is if the language provides you the possibility to do it more effectively. It does: structs and arrays. Yes, my bias is a bias of a C programmer, but there's a reason why good written C code is fast: the number of allocations is small, the most of stuff is preallocated before it's used. D lets you do the same. Note: changing the memory representation of the "objects" you use doesn't suggest you have to change your existing algorithms. It's just how the stuff is stored in memory. The changes to your code then aren't fundamentally significant, but you'll certainly get the initial speedup you need.

acqq 12y ago

How many allocations do you actually make to compile a single variable used 60000 times? I still claim you don't have to allocate much too for that particular input, as long as you use vectors/arrays, the ones you also recognize Bellard probably uses and which I've mentioned in my top comment as the right way to make your code faster. It's really as simple as that.

bmm6o 12y ago
Read the article, please. My implementation of a liveness analysis scales poorly with function size. It allocates a huge bit matrix (vector of bit sets) for liveness computation. This grows quadratically with the function size, which means that in some cases, obscene amounts of memory are required, and this data structure doesn’t fit in the cache
- acqq 12y ago
  The "doesn't fit in the cache" argument has nothing to do with too many small allocations which obviously happen (otherwise GC effects wouldn't be noticeable) and which almost certainly can be replaced with much less allocations of some arrays of things. Which it what I suggest since my top comment.
  - tachyonbeam 12y ago
    From the thread on r/programming: "The main issue from the post is quite simple: if you allocate a lot of small objects, D runtime will place them inside chunks (called pools) of fixed size (like 4 MB) that it requested from the OS. Each time a pool is filled up it will do a GC cycle and only if there's still no room for new object it will allocate a new pool. That means number of GC cycles in this situation is proportional to number of objects you allocate, while each GC cycle time is proportional to the managed heap size. It leads to quadratic complexity and awful slowness. If runtime allocated pools not of fixed size but adapted their size to the allocation rate, this scenario could be significantly faster."
tachyonbeam 12y ago
This isn't C, it's JavaScript. The semantics of a global variable read are a more complicated than you think. Global variables reside on the global object, which can grow dynamically. Global properties can also be deleted at any time. Accessing a property which doesn't exist should throw an exception. Properties could also be getter functions, which would then result in a function call for every property read. Have you written a JS compiler? Have you written a JIT compiler? Any kind of compiler for a real-world language? A garbage collector? If someone knows of a way to get allocation statistics, then I can answer the question of how many allocations occur.
- acqq 12y ago
  > Global variables reside on the global object, which can grow dynamically. But it the example you give there's only one single variable. > Global properties can also be deleted at any time. Also doesn't happen in your example. > Accessing a property which doesn't exist should throw an exception. I agree. > Properties could also be getter functions, which would then result in a function call for every property read. But they aren't in your example. And all these aspects result in proportional increase in the resulting code, not in some unexpected complexity. > If someone knows of a way to get allocation statistics Run a Perl script (or Python script or do it by hand) that adds an increment of global nAllocations variable in front of any statement where you do a "new" of something. (If the most of the allocations are implicit, this counting maybe has to be added to the runtime of D, if it already doesn't exist. At least the runtime is open source, AFAIK). Run the program. Print that number. My guess is that it must be an order of 6 digits (millions) for the performance you measure. Which doesn't seem to be necessary to process 60000 evaluations of a single variable if more arrays of fixed sized things could be used in the process. I know for you it's "doctor, it hurts me when I press me here" "well don't do that" moment, but really, that's how it is. A lot of small objects allocated separately makes a lot of work for a GC and it's so in every language. The question is if the language provides you the possibility to do it more effectively. It does: structs and arrays. Yes, my bias is a bias of a C programmer, but there's a reason why good written C code is fast: the number of allocations is small, the most of stuff is preallocated before it's used. D lets you do the same. Note: changing the memory representation of the "objects" you use doesn't suggest you have to change your existing algorithms. It's just how the stuff is stored in memory. The changes to your code then aren't fundamentally significant, but you'll certainly get the initial speedup you need.