Category: algorithm

This blog is an aggregate of  clever questions and answers about Programming, Coding, and Algorithms. This is a safe place for programmers who are interested in optimizing their code, learning to code for the first time, or just want to be surrounded by the coding environment. 

Console.CancelKeyPress +=
    (sender, e) => {
        Console.WriteLine("CTRL+C detected!\n");
        e.Cancel = true;
    };

string result = value1 ?? value2 ?? value3 ?? String.Empty;

private IList<Foo> _foo;

public IList<Foo> ListOfFoo 
    { get { return _foo ?? (_foo = new List<Foo>()); } }

__makeref

__reftype

__refvalue

__arglist

var @object = new object();
var @string = "";
var @if = IpsoFacto();

Environment.FailFast()

 L  - Linux
 W  - Windows
 M  - Mac
 C  - Commercial
 F  - Free
 CF - Commercial with Free limited edition
 ?  - To be confirmed

application/json

Example: { "Name": "Foo", "Id": 1234, "Rank": 7 }

application/json.

What and where are the stack and the heap?

• Where and what are they (physically in a real computer’s memory)?
• To what extent are they controlled by the OS or language run-time?
• What is their scope?
• What determines the size of each of them?
• What makes one faster?

The stack is the memory set aside as scratch space for a thread of execution. When a function is called, a block is reserved on the top of the stack for local variables and some bookkeeping data. When that function returns, the block becomes unused and can be used the next time a function is called. The stack is always reserved in a LIFO (last in first out) order; the most recently reserved block is always the next block to be freed. This makes it really simple to keep track of the stack; freeing a block from the stack is nothing more than adjusting one pointer.

The heap is memory set aside for dynamic allocation. Unlike the stack, there’s no enforced pattern to the allocation and deallocation of blocks from the heap; you can allocate a block at any time and free it at any time. This makes it much more complex to keep track of which parts of the heap are allocated or free at any given time; there are many custom heap allocators available to tune heap performance for different usage patterns.

Each thread gets a stack, while there’s typically only one heap for the application (although it isn’t uncommon to have multiple heaps for different types of allocation).

To answer your questions directly:

To what extent are they controlled by the OS or language runtime?

The OS allocates the stack for each system-level thread when the thread is created. Typically the OS is called by the language runtime to allocate the heap for the application.

What is their scope?

The stack is attached to a thread, so when the thread exits the stack is reclaimed. The heap is typically allocated at application startup by the runtime, and is reclaimed when the application (technically process) exits.

What determines the size of each of them?

The size of the stack is set when a thread is created. The size of the heap is set on application startup, but can grow as space is needed (the allocator requests more memory from the operating system).

What makes one faster?

The stack is faster because the access pattern makes it trivial to allocate and deallocate memory from it (a pointer/integer is simply incremented or decremented), while the heap has much more complex bookkeeping involved in an allocation or deallocation. Also, each byte in the stack tends to be reused very frequently which means it tends to be mapped to the processor’s cache, making it very fast. Another performance hit for the heap is that the heap, being mostly a global resource, typically has to be multi-threading safe, i.e. each allocation and deallocation needs to be – typically – synchronized with “all” other heap accesses in the program.

A clear demonstration: 
_{Image source: vikashazrati.wordpress.com}

Stack:

• Stored in computer RAM just like the heap.
• Variables created on the stack will go out of scope and are automatically deallocated.
• Much faster to allocate in comparison to variables on the heap.
• Implemented with an actual stack data structure.
• Stores local data, return addresses, used for parameter passing.
• Can have a stack overflow when too much of the stack is used (mostly from infinite or too deep recursion, very large allocations).
• Data created on the stack can be used without pointers.
• You would use the stack if you know exactly how much data you need to allocate before compile time and it is not too big.
• Usually has a maximum size already determined when your program starts.

Heap:

• Stored in computer RAM just like the stack.
• In C++, variables on the heap must be destroyed manually and never fall out of scope. The data is freed with delete, delete[], or free.
• Slower to allocate in comparison to variables on the stack.
• Used on demand to allocate a block of data for use by the program.
• Can have fragmentation when there are a lot of allocations and deallocations.
• In C++ or C, data created on the heap will be pointed to by pointers and allocated with new or malloc respectively.
• Can have allocation failures if too big of a buffer is requested to be allocated.
• You would use the heap if you don’t know exactly how much data you will need at run time or if you need to allocate a lot of data.
• Responsible for memory leaks.

Example:

int foo()
{
  char *pBuffer; //<--nothing allocated yet (excluding the pointer itself, which is allocated here on the stack).
  bool b = true; // Allocated on the stack.
  if(b)
  {
    //Create 500 bytes on the stack
    char buffer[500];

    //Create 500 bytes on the heap
    pBuffer = new char[500];

   }//<-- buffer is deallocated here, pBuffer is not
}//<--- oops there's a memory leak, I should have called delete[] pBuffer;

he most important point is that heap and stack are generic terms for ways in which memory can be allocated. They can be implemented in many different ways, and the terms apply to the basic concepts.

• In a stack of items, items sit one on top of the other in the order they were placed there, and you can only remove the top one (without toppling the whole thing over).

  

  The simplicity of a stack is that you do not need to maintain a table containing a record of each section of allocated memory; the only state information you need is a single pointer to the end of the stack. To allocate and de-allocate, you just increment and decrement that single pointer. Note: a stack can sometimes be implemented to start at the top of a section of memory and extend downwards rather than growing upwards.

• In a heap, there is no particular order to the way items are placed. You can reach in and remove items in any order because there is no clear ‘top’ item.

  

  Heap allocation requires maintaining a full record of what memory is allocated and what isn’t, as well as some overhead maintenance to reduce fragmentation, find contiguous memory segments big enough to fit the requested size, and so on. Memory can be deallocated at any time leaving free space. Sometimes a memory allocator will perform maintenance tasks such as defragmenting memory by moving allocated memory around, or garbage collecting – identifying at runtime when memory is no longer in scope and deallocating it.

These images should do a fairly good job of describing the two ways of allocating and freeing memory in a stack and a heap. Yum!

• To what extent are they controlled by the OS or language runtime?

  As mentioned, heap and stack are general terms, and can be implemented in many ways. Computer programs typically have a stack called a call stack which stores information relevant to the current function such as a pointer to whichever function it was called from, and any local variables. Because functions call other functions and then return, the stack grows and shrinks to hold information from the functions further down the call stack. A program doesn’t really have runtime control over it; it’s determined by the programming language, OS and even the system architecture.

  A heap is a general term used for any memory that is allocated dynamically and randomly; i.e. out of order. The memory is typically allocated by the OS, with the application calling API functions to do this allocation. There is a fair bit of overhead required in managing dynamically allocated memory, which is usually handled by the runtime code of the programming language or environment used.

• What is their scope?

  The call stack is such a low level concept that it doesn’t relate to ‘scope’ in the sense of programming. If you disassemble some code you’ll see relative pointer style references to portions of the stack, but as far as a higher level language is concerned, the language imposes its own rules of scope. One important aspect of a stack, however, is that once a function returns, anything local to that function is immediately freed from the stack. That works the way you’d expect it to work given how your programming languages work. In a heap, it’s also difficult to define. The scope is whatever is exposed by the OS, but your programming language probably adds its rules about what a “scope” is in your application. The processor architecture and the OS use virtual addressing, which the processor translates to physical addresses and there are page faults, etc. They keep track of what pages belong to which applications. You never really need to worry about this, though, because you just use whatever method your programming language uses to allocate and free memory, and check for errors (if the allocation/freeing fails for any reason).

• What determines the size of each of them?

  Again, it depends on the language, compiler, operating system and architecture. A stack is usually pre-allocated, because by definition it must be contiguous memory. The language compiler or the OS determine its size. You don’t store huge chunks of data on the stack, so it’ll be big enough that it should never be fully used, except in cases of unwanted endless recursion (hence, “stack overflow”) or other unusual programming decisions.

  A heap is a general term for anything that can be dynamically allocated. Depending on which way you look at it, it is constantly changing size. In modern processors and operating systems the exact way it works is very abstracted anyway, so you don’t normally need to worry much about how it works deep down, except that (in languages where it lets you) you mustn’t use memory that you haven’t allocated yet or memory that you have freed.

• What makes one faster?

  The stack is faster because all free memory is always contiguous. No list needs to be maintained of all the segments of free memory, just a single pointer to the current top of the stack. Compilers usually store this pointer in a special, fast register for this purpose. What’s more, subsequent operations on a stack are usually concentrated within very nearby areas of memory, which at a very low level is good for optimization by the processor on-die caches.

• Both the stack and the heap are memory areas allocated from the underlying operating system (often virtual memory that is mapped to physical memory on demand).
• In a multi-threaded environment each thread will have its own completely independent stack but they will share the heap. Concurrent access has to be controlled on the heap and is not possible on the stack.

The heap

• The heap contains a linked list of used and free blocks. New allocations on the heap (by new or malloc) are satisfied by creating a suitable block from one of the free blocks. This requires updating the list of blocks on the heap. This meta information about the blocks on the heap is also stored on the heap often in a small area just in front of every block.
• As the heap grows new blocks are often allocated from lower addresses towards higher addresses. Thus you can think of the heap as a heap of memory blocks that grows in size as memory is allocated. If the heap is too small for an allocation the size can often be increased by acquiring more memory from the underlying operating system.
• Allocating and deallocating many small blocks may leave the heap in a state where there are a lot of small free blocks interspersed between the used blocks. A request to allocate a large block may fail because none of the free blocks are large enough to satisfy the allocation request even though the combined size of the free blocks may be large enough. This is called heap fragmentation.
• When a used block that is adjacent to a free block is deallocated the new free block may be merged with the adjacent free block to create a larger free block effectively reducing the fragmentation of the heap.

The stack

• The stack often works in close tandem with a special register on the CPU named the stack pointer. Initially the stack pointer points to the top of the stack (the highest address on the stack).
• The CPU has special instructions for pushing values onto the stack and popping them off the stack. Each push stores the value at the current location of the stack pointer and decreases the stack pointer. A pop retrieves the value pointed to by the stack pointer and then increases the stack pointer (don’t be confused by the fact that adding a value to the stack decreases the stack pointer and removing a value increases it. Remember that the stack grows to the bottom). The values stored and retrieved are the values of the CPU registers.
• If a function has parameters, these are pushed onto the stack before the call to the function. The code in the function is then able to navigate up the stack from the current stack pointer to locate these values.
• When a function is called the CPU uses special instructions that push the current instruction pointer onto the stack, i.e. the address of the code executing on the stack. The CPU then jumps to the function by setting the instruction pointer to the address of the function called. Later, when the function returns, the old instruction pointer is popped off the stack and execution resumes at the code just after the call to the function.
• When a function is entered, the stack pointer is decreased to allocate more space on the stack for local (automatic) variables. If the function has one local 32 bit variable four bytes are set aside on the stack. When the function returns, the stack pointer is moved back to free the allocated area.
• Nesting function calls work like a charm. Each new call will allocate function parameters, the return address and space for local variables and these activation records can be stacked for nested calls and will unwind in the correct way when the functions return.
• As the stack is a limited block of memory, you can cause a stack overflow by calling too many nested functions and/or allocating too much space for local variables. Often the memory area used for the stack is set up in such a way that writing below the bottom (the lowest address) of the stack will trigger a trap or exception in the CPU. This exceptional condition can then be caught by the runtime and converted into some kind of stack overflow exception.

Can a function be allocated on the heap instead of a stack?

No, activation records for functions (i.e. local or automatic variables) are allocated on the stack that is used not only to store these variables, but also to keep track of nested function calls.

How the heap is managed is really up to the runtime environment. C uses malloc and C++ uses new, but many other languages have garbage collection.

However, the stack is a more low-level feature closely tied to the processor architecture. Growing the heap when there is not enough space isn’t too hard since it can be implemented in the library call that handles the heap. However, growing the stack is often impossible as the stack overflow only is discovered when it is too late; and shutting down the thread of execution is the only viable option.

In the following C# code

public void Method1()
{
    int i = 4;
    int y = 2;
    class1 cls1 = new class1();
}

Here’s how the memory is managed

Local Variables that only need to last as long as the function invocation go in the stack. The heap is used for variables whose lifetime we don’t really know up front but we expect them to last a while. In most languages it’s critical that we know at compile time how large a variable is if we want to store it on the stack.

Objects (which vary in size as we update them) go on the heap because we don’t know at creation time how long they are going to last. In many languages the heap is garbage collected to find objects (such as the cls1 object) that no longer have any references.

In Java, most objects go directly into the heap. In languages like C / C++, structs and classes can often remain on the stack when you’re not dealing with pointers.

More information can be found here:

The difference between stack and heap memory allocation « timmurphy.org

and here:

Creating Objects on the Stack and Heap

This article is the source of picture above: Six important .NET concepts: Stack, heap, value types, reference types, boxing, and unboxing – CodeProject

but be aware it may contain some inaccuracies.

The Stack When you call a function the arguments to that function plus some other overhead is put on the stack. Some info (such as where to go on return) is also stored there. When you declare a variable inside your function, that variable is also allocated on the stack.

Deallocating the stack is pretty simple because you always deallocate in the reverse order in which you allocate. Stack stuff is added as you enter functions, the corresponding data is removed as you exit them. This means that you tend to stay within a small region of the stack unless you call lots of functions that call lots of other functions (or create a recursive solution).

The Heap The heap is a generic name for where you put the data that you create on the fly. If you don’t know how many spaceships your program is going to create, you are likely to use the new (or malloc or equivalent) operator to create each spaceship. This allocation is going to stick around for a while, so it is likely we will free things in a different order than we created them.

Thus, the heap is far more complex, because there end up being regions of memory that are unused interleaved with chunks that are – memory gets fragmented. Finding free memory of the size you need is a difficult problem. This is why the heap should be avoided (though it is still often used).

Implementation Implementation of both the stack and heap is usually down to the runtime / OS. Often games and other applications that are performance critical create their own memory solutions that grab a large chunk of memory from the heap and then dish it out internally to avoid relying on the OS for memory.

This is only practical if your memory usage is quite different from the norm – i.e for games where you load a level in one huge operation and can chuck the whole lot away in another huge operation.

Physical location in memory This is less relevant than you think because of a technology called Virtual Memory which makes your program think that you have access to a certain address where the physical data is somewhere else (even on the hard disc!). The addresses you get for the stack are in increasing order as your call tree gets deeper. The addresses for the heap are un-predictable (i.e implimentation specific) and frankly not important.

In Short

A stack is used for static memory allocation and a heap for dynamic memory allocation, both stored in the computer’s RAM.

In Detail

The Stack

The stack is a “LIFO” (last in, first out) data structure, that is managed and optimized by the CPU quite closely. Every time a function declares a new variable, it is “pushed” onto the stack. Then every time a function exits, all of the variables pushed onto the stack by that function, are freed (that is to say, they are deleted). Once a stack variable is freed, that region of memory becomes available for other stack variables.

The advantage of using the stack to store variables, is that memory is managed for you. You don’t have to allocate memory by hand, or free it once you don’t need it any more. What’s more, because the CPU organizes stack memory so efficiently, reading from and writing to stack variables is very fast.

More can be found here.

The Heap

The heap is a region of your computer’s memory that is not managed automatically for you, and is not as tightly managed by the CPU. It is a more free-floating region of memory (and is larger). To allocate memory on the heap, you must use malloc() or calloc(), which are built-in C functions. Once you have allocated memory on the heap, you are responsible for using free() to deallocate that memory once you don’t need it any more.

If you fail to do this, your program will have what is known as a memory leak. That is, memory on the heap will still be set aside (and won’t be available to other processes). As we will see in the debugging section, there is a tool called Valgrind that can help you detect memory leaks.

Unlike the stack, the heap does not have size restrictions on variable size (apart from the obvious physical limitations of your computer). Heap memory is slightly slower to be read from and written to, because one has to use pointers to access memory on the heap. We will talk about pointers shortly.

Unlike the stack, variables created on the heap are accessible by any function, anywhere in your program. Heap variables are essentially global in scope.

More can be found here.

Variables allocated on the stack are stored directly to the memory and access to this memory is very fast, and its allocation is dealt with when the program is compiled. When a function or a method calls another function which in turns calls another function, etc., the execution of all those functions remains suspended until the very last function returns its value. The stack is always reserved in a LIFO order, the most recently reserved block is always the next block to be freed. This makes it really simple to keep track of the stack, freeing a block from the stack is nothing more than adjusting one pointer.

Variables allocated on the heap have their memory allocated at run time and accessing this memory is a bit slower, but the heap size is only limited by the size of virtual memory. Elements of the heap have no dependencies with each other and can always be accessed randomly at any time. You can allocate a block at any time and free it at any time. This makes it much more complex to keep track of which parts of the heap are allocated or free at any given time.

You can use the stack if you know exactly how much data you need to allocate before compile time, and it is not too big. You can use the heap if you don’t know exactly how much data you will need at runtime or if you need to allocate a lot of data.

In a multi-threaded situation each thread will have its own completely independent stack, but they will share the heap. The stack is thread specific and the heap is application specific. The stack is important to consider in exception handling and thread executions.

Each thread gets a stack, while there’s typically only one heap for the application (although it isn’t uncommon to have multiple heaps for different types of allocation).

At run-time, if the application needs more heap, it can allocate memory from free memory and if the stack needs memory, it can allocate memory from free memory allocated memory for the application.

Even, more detail is given here and here.

Now come to your question’s answers.

To what extent are they controlled by the OS or language runtime?

The OS allocates the stack for each system-level thread when the thread is created. Typically the OS is called by the language runtime to allocate the heap for the application.

More can be found here.

What is their scope?

Already given in top.

“You can use the stack if you know exactly how much data you need to allocate before compile time, and it is not too big. You can use the heap if you don’t know exactly how much data you will need at runtime or if you need to allocate a lot of data.”

More can be found in here.

What determines the size of each of them?

The size of the stack is set by OS when a thread is created. The size of the heap is set on application startup, but it can grow as space is needed (the allocator requests more memory from the operating system).

What makes one faster?

Stack allocation is much faster since all it really does is move the stack pointer. Using memory pools, you can get comparable performance out of heap allocation, but that comes with a slight added complexity and its own headaches.

Also, stack vs. heap is not only a performance consideration; it also tells you a lot about the expected lifetime of objects.

Details can be found from here.

How do you stop scripters from slamming your website hundreds of times a second?

How about implementing something like SO does with the CAPTCHAs?

If you’re using the site normally, you’ll probably never see one. If you happen to reload the same page too often, post successive comments too quickly, or something else that triggers an alarm, make them prove they’re human. In your case, this would probably be constant reloads of the same page, following every link on a page quickly, or filling in an order form too fast to be human.

If they fail the check x times in a row (say, 2 or 3), give that IP a timeout or other such measure. Then at the end of the timeout, dump them back to the check again.

Since you have unregistered users accessing the site, you do have only IPs to go on. You can issue sessions to each browser and track that way if you wish. And, of course, throw up a human-check if too many sessions are being (re-)created in succession (in case a bot keeps deleting the cookie).

As far as catching too many innocents, you can put up a disclaimer on the human-check page: “This page may also appear if too many anonymous users are viewing our site from the same location. We encourage you to register or login to avoid this.” (Adjust the wording appropriately.)

Besides, what are the odds that X people are loading the same page(s) at the same time from one IP? If they’re high, maybe you need a different trigger mechanism for your bot alarm.

Edit: Another option is if they fail too many times, and you’re confident about the product’s demand, to block them and make them personally CALL you to remove the block.

Having people call does seem like an asinine measure, but it makes sure there’s a human somewhere behind the computer. The key is to have the block only be in place for a condition which should almost never happen unless it’s a bot (e.g. fail the check multiple times in a row). Then it FORCES human interaction – to pick up the phone.

In response to the comment of having them call me, there’s obviously that tradeoff here. Are you worried enough about ensuring your users are human to accept a couple phone calls when they go on sale? If I were so concerned about a product getting to human users, I’d have to make this decision, perhaps sacrificing a (small) bit of my time in the process.

Since it seems like you’re determined to not let bots get the upper hand/slam your site, I believe the phone may be a good option. Since I don’t make a profit off your product, I have no interest in receiving these calls. Were you to share some of that profit, however, I may become interested. As this is your product, you have to decide how much you care and implement accordingly.

The other ways of releasing the block just aren’t as effective: a timeout (but they’d get to slam your site again after, rinse-repeat), a long timeout (if it was really a human trying to buy your product, they’d be SOL and punished for failing the check), email (easily done by bots), fax (same), or snail mail (takes too long).

You could, of course, instead have the timeout period increase per IP for each time they get a timeout. Just make sure you’re not punishing true humans inadvertently.

Performance optimization strategies as a last resort

Let’s assume:

• the code already is working correctly
• the algorithms chosen are already optimal for the circumstances of the problem
• the code has been measured, and the offending routines have been isolated
• all attempts to optimize will also be measured to ensure they do not make matters worse

OK, you’re defining the problem to where it would seem there is not much room for improvement. That is fairly rare, in my experience. I tried to explain this in a Dr. Dobbs article in November 1993, by starting from a conventionally well-designed non-trivial program with no obvious waste and taking it through a series of optimizations until its wall-clock time was reduced from 48 seconds to 1.1 seconds, and the source code size was reduced by a factor of 4. My diagnostic tool was this. The sequence of changes was this:

• The first problem found was use of list clusters (now called “iterators” and “container classes”) accounting for over half the time. Those were replaced with fairly simple code, bringing the time down to 20 seconds.

• Now the largest time-taker is more list-building. As a percentage, it was not so big before, but now it is because the bigger problem was removed. I find a way to speed it up, and the time drops to 17 seconds.

• Now it is harder to find obvious culprits, but there are a few smaller ones that I can do something about, and the time drops to 13 sec.

Now I seem to have hit a wall. The samples are telling me exactly what it is doing, but I can’t seem to find anything that I can improve. Then I reflect on the basic design of the program, on its transaction-driven structure, and ask if all the list-searching that it is doing is actually mandated by the requirements of the problem.

Then I hit upon a re-design, where the program code is actually generated (via preprocessor macros) from a smaller set of source, and in which the program is not constantly figuring out things that the programmer knows are fairly predictable. In other words, don’t “interpret” the sequence of things to do, “compile” it.

• That redesign is done, shrinking the source code by a factor of 4, and the time is reduced to 10 seconds.

Now, because it’s getting so quick, it’s hard to sample, so I give it 10 times as much work to do, but the following times are based on the original workload.

• More diagnosis reveals that it is spending time in queue-management. In-lining these reduces the time to 7 seconds.

• Now a big time-taker is the diagnostic printing I had been doing. Flush that – 4 seconds.

• Now the biggest time-takers are calls to malloc and free. Recycle objects – 2.6 seconds.

• Continuing to sample, I still find operations that are not strictly necessary – 1.1 seconds.

Total speedup factor: 43.6

Now no two programs are alike, but in non-toy software I’ve always seen a progression like this. First you get the easy stuff, and then the more difficult, until you get to a point of diminishing returns. Then the insight you gain may well lead to a redesign, starting a new round of speedups, until you again hit diminishing returns. Now this is the point at which it might make sense to wonder whether ++i or i++ or for(;;) or while(1) are faster: the kinds of questions I see so often on Stack Overflow.

P.S. It may be wondered why I didn’t use a profiler. The answer is that almost every one of these “problems” was a function call site, which stack samples pinpoint. Profilers, even today, are just barely coming around to the idea that statements and call instructions are more important to locate, and easier to fix, than whole functions.

I actually built a profiler to do this, but for a real down-and-dirty intimacy with what the code is doing, there’s no substitute for getting your fingers right in it. It is not an issue that the number of samples is small, because none of the problems being found are so tiny that they are easily missed.

ADDED: jerryjvl requested some examples. Here is the first problem. It consists of a small number of separate lines of code, together taking over half the time:

 /* IF ALL TASKS DONE, SEND ITC_ACKOP, AND DELETE OP */
if (ptop->current_task >= ILST_LENGTH(ptop->tasklist){
. . .
/* FOR EACH OPERATION REQUEST */
for ( ptop = ILST_FIRST(oplist); ptop != NULL; ptop = ILST_NEXT(oplist, ptop)){
. . .
/* GET CURRENT TASK */
ptask = ILST_NTH(ptop->tasklist, ptop->current_task)

These were using the list cluster ILST (similar to a list class). They are implemented in the usual way, with “information hiding” meaning that the users of the class were not supposed to have to care how they were implemented. When these lines were written (out of roughly 800 lines of code) thought was not given to the idea that these could be a “bottleneck” (I hate that word). They are simply the recommended way to do things. It is easy to say in hindsight that these should have been avoided, but in my experience all performance problems are like that. In general, it is good to try to avoid creating performance problems. It is even better to find and fix the ones that are created, even though they “should have been avoided” (in hindsight). I hope that gives a bit of the flavor.

Here is the second problem, in two separate lines:

 /* ADD TASK TO TASK LIST */
ILST_APPEND(ptop->tasklist, ptask)
. . .
/* ADD TRANSACTION TO TRANSACTION QUEUE */
ILST_APPEND(trnque, ptrn)

These are building lists by appending items to their ends. (The fix was to collect the items in arrays, and build the lists all at once.) The interesting thing is that these statements only cost (i.e. were on the call stack) 3/48 of the original time, so they were not in fact a big problem at the beginning. However, after removing the first problem, they cost 3/20 of the time and so were now a “bigger fish”. In general, that’s how it goes.

I might add that this project was distilled from a real project I helped on. In that project, the performance problems were far more dramatic (as were the speedups), such as calling a database-access routine within an inner loop to see if a task was finished.

REFERENCE ADDED: The source code, both original and redesigned, can be found in www.ddj.com, for 1993, in file 9311.zip, files slug.asc and slug.zip.

EDIT 2011/11/26: There is now a SourceForge project containing source code in Visual C++ and a blow-by-blow description of how it was tuned. It only goes through the first half of the scenario described above, and it doesn’t follow exactly the same sequence, but still gets a 2-3 order of magnitude speedup.

Suggestions:

• Pre-compute rather than re-calculate: any loops or repeated calls that contain calculations that have a relatively limited range of inputs, consider making a lookup (array or dictionary) that contains the result of that calculation for all values in the valid range of inputs. Then use a simple lookup inside the algorithm instead.
  Down-sides: if few of the pre-computed values are actually used this may make matters worse, also the lookup may take significant memory.
• Don’t use library methods: most libraries need to be written to operate correctly under a broad range of scenarios, and perform null checks on parameters, etc. By re-implementing a method you may be able to strip out a lot of logic that does not apply in the exact circumstance you are using it.
  Down-sides: writing additional code means more surface area for bugs.
• Do use library methods: to contradict myself, language libraries get written by people that are a lot smarter than you or me; odds are they did it better and faster. Do not implement it yourself unless you can actually make it faster (i.e.: always measure!)
• Cheat: in some cases although an exact calculation may exist for your problem, you may not need ‘exact’, sometimes an approximation may be ‘good enough’ and a lot faster in the deal. Ask yourself, does it really matter if the answer is out by 1%? 5%? even 10%?
  Down-sides: Well… the answer won’t be exact.

When you can’t improve the performance any more – see if you can improve the perceived performance instead.

You may not be able to make your fooCalc algorithm faster, but often there are ways to make your application seem more responsive to the user.

A few examples:

• anticipating what the user is going to request and start working on that before then
• displaying results as they come in, instead of all at once at the end
• Accurate progress meter

These won’t make your program faster, but it might make your users happier with the speed you have.

I spend most of my life in just this place. The broad strokes are to run your profiler and get it to record:

• Cache misses. Data cache is the #1 source of stalls in most programs. Improve cache hit rate by reorganizing offending data structures to have better locality; pack structures and numerical types down to eliminate wasted bytes (and therefore wasted cache fetches); prefetch data wherever possible to reduce stalls.
• Load-hit-stores. Compiler assumptions about pointer aliasing, and cases where data is moved between disconnected register sets via memory, can cause a certain pathological behavior that causes the entire CPU pipeline to clear on a load op. Find places where floats, vectors, and ints are being cast to one another and eliminate them. Use __restrict liberally to promise the compiler about aliasing.
• Microcoded operations. Most processors have some operations that cannot be pipelined, but instead run a tiny subroutine stored in ROM. Examples on the PowerPC are integer multiply, divide, and shift-by-variable-amount. The problem is that the entire pipeline stops dead while this operation is executing. Try to eliminate use of these operations or at least break them down into their constituent pipelined ops so you can get the benefit of superscalar dispatch on whatever the rest of your program is doing.
• Branch mispredicts. These too empty the pipeline. Find cases where the CPU is spending a lot of time refilling the pipe after a branch, and use branch hinting if available to get it to predict correctly more often. Or better yet, replace branches with conditional-moves wherever possible, especially after floating point operations because their pipe is usually deeper and reading the condition flags after fcmp can cause a stall.
• Sequential floating-point ops. Make these SIMD.

And one more thing I like to do:

• Set your compiler to output assembly listings and look at what it emits for the hotspot functions in your code. All those clever optimizations that “a good compiler should be able to do for you automatically”? Chances are your actual compiler doesn’t do them. I’ve seen GCC emit truly WTF code.

More suggestions:

• Avoid I/O: Any I/O (disk, network, ports, etc.) is always going to be far slower than any code that is performing calculations, so get rid of any I/O that you do not strictly need.

• Move I/O up-front: Load up all the data you are going to need for a calculation up-front, so that you do not have repeated I/O waits within the core of a critical algorithm (and maybe as a result repeated disk seeks, when loading all the data in one hit may avoid seeking).

• Delay I/O: Do not write out your results until the calculation is over, store them in a data structure and then dump that out in one go at the end when the hard work is done.

• Threaded I/O: For those daring enough, combine ‘I/O up-front’ or ‘Delay I/O’ with the actual calculation by moving the loading into a parallel thread, so that while you are loading more data you can work on a calculation on the data you already have, or while you calculate the next batch of data you can simultaneously write out the results from the last batch.

How much faster is C compared to Python?

Run Your Python Code Online Here

I’m currently coding a SAT solver algorithm that will have to take millions of input data, and I was wondering if I should switch from Python to C.

Answer: Using best-of-class equivalent algorithms optimized compiled C code is often multiple orders of magnitude faster than Python code interpreted by CPython (the main Python implementation). Other Python implementations (like PyPy) might be a bit better, but not vastly so. Some computations fit Python better, but I have a feeling that a SAT solver implementation will not be competitive if written using Python.

All that said, do you need to write a new implementation? Could you use one of the excellent ones out there? CDCL implementations often do a good job, and there are various open-source ones readily available (e.g., this one: https://github.com/togatoga/togasat

Comments:

1- I mean, also it depends. I recall seeing an analysis some time ago, that showed CPython can be as fast as C … provided you are almost exclusively using library functions written in C. That being said, for any non-trivial python program it will probably be the case that you must spend quite a bit of time in the interpreter, and not in C library functions.

In C++, what is the difference between calling the class’ variable or method by double colons (::) and by the dot (.)?

 

The dot operator’s left hand operand is an object reference, which is needed for the access to contextualize with said object’s state.

The double colon operator has two uses in this case:

• Access to a static class member.
• Access to a parent class member (needs the context of a running method which can be static or not).

Why Rust?

There are two main reasons: performance and familiarity. While Rust has been shown to be faster than C++, it’s not as fast as assembly language—and many developers have been working in assembly for so long that they’re not willing to give it up.

However, there’s another reason why some developers are sticking with C++: compiler optimization.

C++ compilers are more intelligent than Rust compilers when it comes to optimizing code for performance, so if you’re looking for top-notch performance from your application, then you might want to stick with C++ until the Rust compiler has caught up.

What is C++ written in?

The C++ programming language definition is written in English and in other human languages. Programming language definitions are written for humans to read. They are not written in programming languages.

An actual implementation of a C++ compiler (or interpreter) can be written in any general-purpose programming language. Some are written in C, some are written in C++, some are written in other programming languages. Some are written with the help of compiler development tools and infrastructure (e.g., lex, yacc, flex, bison, antlr, LLVM, etc.). It just depends on the specific C++ implementation you’re looking at.

This is true of all high-level programming languages. Any general-purpose programming language can be used to implement a compiler or interpreter, no matter what programming language you are compiling or interpreting.

How useful is C++ nowadays? Should I start anything else in the future? How useful will it be in the job market? Is there anything significant it can’t do?

Learn other languages. It will broaden your perspective and hopefully make you a better developer.

Alan Perlis, one of the developers of ALGOL, once said, “A language that doesn’t affect the way you think about programming, is not worth knowing.”

Conversely, that implies learning other languages can and will affect the way you think about programming, provided you get some variety of exposure.

C++ is a multiparadigm language. But if you haven’t had exposure to those paradigms in a more focused setting, you might not understand the value they bring, or their strengths, weaknesses, idioms, and insights.

So even if you do the bulk of your programming in C++, you may not be using it the most effective way possible.

I know I personally have gaps, because I haven’t explored certain paradigms myself. I owe it to myself to at least dip my toe in some of them. I know this, because every time I learn a new language or environment, I sense a gap closing—a gap I may not have been aware of previously.

You don’t even need to spend a lot of time to gain value, either. I may have only spent a week with Scala, for example, but I learned more than just the base language from it. I hadn’t really encountered fold and match expressions as such basic and integral concepts, for example.

And despite its negative reputation, I found Perl to be an excellent language to learn about multiple programming techniques.

Mark Jason Dominus’ Higher Order Perl opened my eyes a number of techniques that I believe originated more from the LISP world.

---

Example: Partial Function Application

In Perl, you can implement partial function application (sometimes conflated with the related concept currying) with you eyes closed and one hand behind your back. Suppose I want to bind the first argument of foo():

• my $f = sub { return foo(arg1, @_); }; 

Now I can invoke $f as a function with that first argument bound, with a slight syntax tweak: &$f(…) or $f->(…). I don’t even need to think about the rest.

Trying to learn about that for the first time in C++ likely would have lost the forest for the trees.

C++98 was quite primitive. It offered std::bind1st and std::bind2nd for 2-argument function objects only. Boost offered boost::bind,[1] which had its own limitations. And because these were relatively uncommon, they were unfamiliar to many C++ users (at least among the crowd I was in). C++ lambdas (introduced with C++11) help, but they don’t work for arbitrary arguments until C++14. For that, you probably need parameter packs, forwarding references, and std::forward.[2] And then there’s object lifetimes to consider, so for your bound arguments you might need to trade off between copy, move, capturing a reference, smart pointers,[3][4] etc. Oh, and finally, it won’t yield a function pointer, but rather an function object, so it’s not usable in places that need a pure function pointer. Although, if it manages to be capture-less, it can provide a pure function pointer by applying unary + to it…

Can you see how you might lose the forest for the trees here?

If you didn’t already have some idea of the usefulness of partial application, would you even try? If you hadn’t encountered the concept before, would it have even come to mind when you saw lambdas?

---

Punchline

In practice, if you’re already well versed in C++, it’s not actually all that difficult to implement techniques like partial application in C++. You’re already accustomed to the rigamarole described above, since C++ confronts you with those sorts of decisions regularly.

It does cloud things noticeably, however. Learning the concepts in a simpler environment separates you from the implementation noise.

Learn other languages and become a more rounded and hopefully better developer. Step away from C++’s innumerable trees of details to see different areas of the forest more clearly.

Footnotes

[1] Chapter 1. Boost.Bind

[2] std::forward – cppreference.com

[3] std::unique_ptr – cppreference.com

[4] std::shared_ptr – cppreference.com

 

In C++, how can a template object be deleted with or without the delete keyword? (template <class T> class Obj;)

If you allocated it with new, then delete it by passing the pointer to delete, just like any other pointer. There’s nothing particularly special about a pointer to an object whose type happens to be a template.

Most of the time, though, you shouldn’t be calling new and delete directly.

See: https://youtu.be/JfmTagWcqoE

When should “new” be used in C++?

new’s use should be confined to very narrow use-cases. Examples of use cases where new is ok:

1. Writing low-level memory management code such as allocators and deallocators, smart pointers, etc.
2. Working with code/libraries that uses outdated C++ programming idioms like QT — but then narrowly limited to the extent necessary to work with QT
3. You are going to need to preallocate an object to pass to an API that indicates it will assume ownership of (i.e. responsibility for deleting the object and delete). If you are going to work with that object at all before passing it off, you should not use new. (use a unique pointer and call .release(), when calling the API).

The way to dynamically allocate memory correctly in modern C++ is std::make_unique or std::make_shared. The first returns a unique_pointer to the allocated object (which will delete the object for you when it goes out of scope) or std::shared_pointer which can be copied around — the object will be deleted for you when there are no more copies of the shared pointer.

For most programming work, you don’t need and shouldn’t use “new” or even worse “malloc”.

Source: Quora

Why do array indexes start with 0 (zero) in many programming languages?

 

Originally Answered: Why do array indices start with 0 (zero) in many programming languages?

Array indices should start at 0. This is not just an efficiency hack for ancient computers, or a reflection of the underlying memory model, or some other kind of historical accident—forget all of that. Zero-based indexing actually simplifies array-related math for the programmer, and simpler math leads to fewer bugs. Here are some examples.

• Suppose you’re writing a hash table that maps each integer key to one of n buckets. If your array of buckets is indexed starting at 0, you can write bucket = key mod n; but if it’s indexed starting at 1, you have to write bucket = (key mod n) + 1.
• Suppose you’re writing code to serialize a rectangular array of pixels, with width w and height h, to a file (which we’ll think of as a one-dimensional array of length w*h). With 0-indexed arrays, pixel (x, y) goes into position y*w + x; with 1-indexed arrays, pixel (x, y) goes into position y*w + x - w.
• Suppose you want to put the letters ‘A’ through ‘Z’ into an array of length 26, and you have a function ord that maps a character to its ASCII value. With 0-indexed arrays, the character c is put at index ord(c) - ord(‘A’); with 1-indexed arrays, it’s put at index ord(c) - ord(‘A’) + 1.

It’s in fact one-based indexing that’s the historical accident—human languages needed numbers for “first”, “second”, etc. before we had invented zero. For a practical example of the kinds of problems this accident leads to, consider how the 1800s—well, no, actually, the period from January 1, 1801 through December 31, 1900—came to be known as the “19th century”.

Knowing that Python is very slow compared to Java and C++, why do people mostly use Python for fast algorithmic procedures like machine learning?

 

Originally Answered: Knowing that Python is very slow compared to Java and C++, why do they mostly use Python for fast algorithmic procedures like machine learning?

No, almost no one uses Python libraries for machine learning.

Before you start listing counterexamples, notice the emphasized words. Yes, a lot of people use Python for machine learning, because it allows for very fast prototyping and overall exploration of problem space, but none of the libraries they are using for it are actually written in Python. Indeed, they are almost always written in either Fortran or C++ instead, and just interface with Python through some thin wrapper.

The slowness of Python is completely irrelevant if the only thing you do with it is invoking a library function written in highly-optimized C++.

Why is Google still using Java? Which language is better, Java or Python?

 

Originally Answered: Why is Google still using Java. Which language is better Java or Python?

Python’s a great language, but I’m going to mention a few reasons why you might choose Java:

• It’s fast, handles multithreaded well, and scales.
• It’s built for security.
• It has a great ecosystem. (Which includes a deep learning library I work on.)
• Many companies have bet their stack on Java, so there’s demand for Java programmers.
• The JVM is cross-platform, and uses run-time information to manage itself.
• It takes care of memory management.
•  Java 8 has lambda expressions, and includes an impl of Javascript called Nashorn that runs on the JVM.
• Static typing: Java is typesafe, and its static typing is essentially a form of self-documenting code.
• Java is mature: It’s been around for 20 years, it’s fully backward compatible, and code written decades ago still works.
• Android: Java 7 works on the world’s largest mobile OS.

For those and other reasons, Java is one of the world’s most widely used languages. Oracle says there are 10 million Java programmers worldwide. The Github stats from Eduardo Bonet speak volumes.

What exactly is the FizzBuzz task?

It’s a basic programming skills challenge.

If you understand loops, variables and conditionals only, that’s enough to hack out a FizzBuzz. If you’re a bit further along the path, you can write a cleaner FizzBuzz

The challenge itself is about writing fizz and buzz when a number is exactly divisible by 3 or 5. It’s not really important, except that it steers you to use those elements of programming above.

It can be done in any language as those concepts are foundational to every language.

What do most programmers do (when optimizing code) that is essentially wrong?

Let me open with a quote that you’ve probably seen many times:

premature optimization is the root of all evil.
— Donald Knuth

• Programs are regularly gigantic. If you profile a program that isn’t fast enough, you’ll often find histograms that shows the top 1,000 functions all taking well under 0.1% of the execution time. “Optimizing” those 1,000 functions is usually not practical and would likely not achieve the desired speedup anyway.
• The number of executed instructions is often relatively irrelevant. Instead, the number of cache misses is far more critical, but it’s also much harder to locate them. Avoiding cache misses is something that may require design work up front, because it affects core data structures.
• Machines are highly heterogeneous, and extracting performance is not just a matter of dealing with the main CPU cores (which may not be homogeneous!), but also to arrange for efficient use of vector units, and accelerators like GPUs, media co-processors, and neural engines. Utilizing all those units is also something that may require design work up front.
• Performance is not just a matter of execution time. It’s also a matter of energy consumption and scalability. And response time: More than ever, software is interactive, and yet has to deal with new kinds of latencies (e.g., from networking).
• Software is an independent industry: If your version 1.0 is too slow, or uses to much battery life, or chokes your data center, you might not get a chance at developing an optimized version 1.5. (In 1974, software was mostly an add-on to hardware.)
• Software is built from independent components: While developing a specific component, you might not know just how hard it will be pushed. If you don’t design for performance from the start you may end up painting yourself into a corner.

All that to say that Knuth’ quote should be taken for what it is: Don’t optimize local instruction counts early on. But don’t skip thinking about optimizing design and data structures from the start, because if performance matters in any way (throughput, latency, energy use, or scalability) it’s something that’s difficult or impossible to “retrofit”. Things to think about:

• How will you evaluate performance? How will you track it during the development and maintenance process?
• How can you avoid computation that’s not needed? This might mean to architect for “lazy evaluation”.
• How will you lay out your data for efficient access (i.e., make best use of the memory hierarchy)?
• How will you organize your algorithms and data structures to take advantage of the available computational resources?
• When considering algorithms, what regime will they work in? A traditional example: “Fast” sorting algorithms are typically only preferable once there are enough elements (often 50+) to sort; if you know that you’ll be repeatedly sorting a dozen elements, those algorithms may not be your best option.
• Are the complexities introduced to achieve better performance worth their overall (negative?) impact on the project?

When all that is handled adequately, you might eventually have to deal with “nitty gritty code optimization”, and it will have a chance to be meaningful.

Now, regarding the original question:

What do most programmers do (when optimizing code) that is essentially wrong?

 

I don’t think that’s generalizable. I think Knuth’s quote is often mis-construed… but I wouldn’t say that “most programmers” do that. I’m not even sure that “most programmers” optimize code at all. I also think that Knuth’s quote is often ignored, and that’s not great either… but again, I’d venture that it doesn’t involve “most programmers”. Programmers are a very diverse bunch, with many diverse roles, working on a great diversity of projects that may or may not have concrete performance constraints.

In other words, I think the question has no meaningful answer.

Finally, I’d like to close with a quote from the late Len Lattanzi (whom I had the pleasure of having as a colleague for a few years):

Belated pessimization is the leaf of no good.
— Len Lattanzi

Pros and Cons of Java vs Node vs .Net,  Which stack should I go for, .NET, Node, or Java?

Umm, that’s really up to you. But there are some tradeoffs.

Java:

Pros:

Extremely widely used. You’ll never want for a job if you are good at it. Other languages (Scala, Kotlin, Groovy) run on the JVM as well. There is a lot of cool big data processing that you can use Java for (Apache Spark, Hadoop, etc.).

Cons:

Tons of bloatware (WebSphere, WebLogic, Adobe Experience Manager) runs on Java. You’re likely to end up coding up some legacy enterprise garbage. UIs written in Java are crap at best.

.NET:

Pros:

Well supported by Microsoft. Visual Studio is gorgeous.

Cons:

Not so many open source libraries, you’ll likely be coding for Windows. This means that your development machine will be Windows (dealbreaker for me). Also, no cool little startup will use .NET ever. Not as many jobs as Java. UIs written in .NET are crap at best.

Node.js

Pros:

Much more concise and faster to develop for than either .NET or Java. Almost as many open source libraries as there are for Java.

Cons:

Memory management, thread management, and overall performance aren’t as good as Java or .NET. You’ll have a harder time finding a Node.js job unless you also know a client side JS framework such as Vue.js or React.js. In that case, you’ll be very much in demand.

Others:

If you want to stick to server side coding, you should consider RUST and Golang. Both are more performant than any of the above. Benchmarks I’ve read suggest that RUST is overall more performant but that Golang has better concurrency management.

How can I return two objects from a method in Java?

• Inside another object that wraps them
• Two methods returning one object each
• pass in two objects as collaborating parameters so methods can be called on them

The second way is good in OO. You do your calculation once, store the two results as state in an object, use two separate accessors in the calling code.

Do all pointers have the same size in C++?

Theoretically, no. Not even for a given system. A char* may have a size different from an int*.

In practice, yes.

First, note that all pointers to object types (as opposed to function types) must be able to round-trip through void* (modulo cv-qualification). So if different object pointer types had different sizes, void* would have to be as large as the largest of them.

Second, for pointers to object types there aren’t many potential advantages to having them be of different size. Why make things complex if they can be made simple at no perceivable cost?

Third… plenty of reasonable code “out there” assumes that all pointers have the same size. So building an implementation where that’s not the case handicaps that implementation right out of the gate.

For function pointers it may actually sometimes be interesting from a performance point of view to give them twice the size of ordinary pointers, because they may have to encapsulate both the address of the function and the address of the associated data segment (in shared library models where a separate data segment is created for every shared library instance). However, because of compatibility considerations even those implementations just add an indirection to keep the function pointers compatible with void* (even though function pointers are not strictly required by the standard to round-trip through void*).

What is a faster alternative to “if” in coding?

1. Try it and measure it
2. On the scale of bad programming, if is at the bottom of the list.

Compilers are very smart about these things. as an example, consider the alternatives

Both compile to the exact same code sequence, which does NOT include a branch:

Source code is supposed to be a way to express your intent to the computer. You really should write the source to be as clear as possible and leave the microoptimizations to the compiler. Once you get the program working and correct, then you can look at performance. Use profiling tools to figure out where the time is going and speed up the parts that are slow AND where being slow actually matters.

By the way, you shouldn’t be afraid of branches either. The branch prediction logic in modern processors is nearly telepathic. AMD is using neural nets inside the chip (!). The predictors will correctly guess what is going to happen more than 90% of the time.

What does strongly typed mean in programming?

 

The other answers are mistaken. This is a very common confusion. They describe statically typed language, not strongly typed language. There is a big difference.

Strongly typed vs weakly typed:

In strongly typed languages you get an error if the types do not match in an expression. It does not matter if the type is determined at compile time (static types) or runtime (dynamic types).

Both java and python are strongly typed. In both languages, you get an error if you try to add objects with unmatching types. For example, in python, you get an error if you try to add a number and a string:

• >>> a = 10 

• >>> b = “hello” 

• >>> a + b 

• Traceback (most recent call last): 

• File “<stdin>”, line 1, in <module> 

• TypeError: unsupported operand type(s) for +: ‘int’ and ‘str’ 

In Python, you get this error at runtime. In Java, you would get a similar error at compile time. Most statically typed languages are also strongly typed.

The opposite of strongly typed language is weakly typed. In a weakly typed language, there are implicit type conversions. Instead of giving you an error, it will convert one of the values automatically and produce a result, even if such conversion loses data. This often leads to unexpected and unpredictable behavior.

Javascript is an example of a weakly typed language.

• > let a = 10 

• > let b = “hello” 

• > a + b 

• ’10hello’ 

Instead of an error, JavaScript will convert a to string and then concatenate the strings.

Static types vs dynamic types:

In a statically typed language, variables are bound types and may only hold data of that type. Typically you declare variables and specify the type of data that the variable has. In some languages, the type can be deduced from what you assign to it, but it still holds that the variable is bound to that type. For example, in java:

• int a = 3; 

• a = “hello” // Error, a can only contain integers 

in a dynamically typed language, variables may hold any type of data. The type of the data is simply determined by what gets assigned to the variable at runtime. Python is dynamically typed, for example:

• a = 10 

• a = “hello” 

• # no problem, a first held an integer and then a string 

Comments:

#1: Don’t confuse strongly typed with statically typed.

Python is dynamically typed and strongly typed.
Javascript is dynamically typed and weakly typed.
Java is statically typed and strongly typed.
C is statically typed and weekly typed.

See these articles for a longer explanation:
Magic lies here – Statically vs Dynamically Typed Languages
Key differences between mainly used languages for data science

I also added a drawing that illustrates how strong and static typing relate to each other:

Python is dynamically typed because types are determined at runtime. The opposite of dynamically typed is statically typed (not strongly typed)

Python is strongly typed because it will give errors when types don’t match instead of performing implicit conversion. The opposite of strongly typed is weakly typed

Python is strongly typed and dynamically typed

What is the difference between finalize() and destructor in Java?

Finalize() is not guaranteed to be called and the programmer has no control over what time or in what order finalizers are called.

They are useless and should be ignored.

A destructor is not part of Java. It is a C++ language feature with very precise definitions of when it will be called.

Comments:

1- Until we got to languages like Rust (with the Drop trait) and a few others was C++ the only language which had the destructor as a concept? I feel like other languages were inspired from that.

2- Many others manage memory for you, even predating C: COBOL, FORTRAN and so on. That’s another driver why there isn’t much attention to destructors

What are some ways to avoid writing static helper classes in Java?

Mainly getting out of that procedural ‘function operates on parameters passed in’ mindset.

Tactically, the static can normally be moved onto one of the parameter objects. Or all the parameters become an object that the static moves to. A new object might be needed. Once done the static is now a fully fledged method on an object and is not static anymore.

I view this as a positive iterative step in discovering objects for a system.

For cases where a static makes sense (? none come to mind) then a good practice is to move it closer to where it is used either in the same package or on a class that is strongly related.

I avoid having global ‘Utils’ classes full of statics that are unrelated. That’s fairly basic design, keeping unrelated things separate. In this case, the SOLID ISP principle applies: segregate into smaller, more focused interfaces.

Is there any programming language as easy as python and as fast and efficient as C++, if yes why it’s not used very often instead of C or C++ in low level programming like embedded systems, AAA 2D and 3D video games, or robotic?

Not really. I use Python occasionally for “quick hacks” – programs that I’ll probably run once and then delete – also, because I use “blender” for 3D modeling and Python is it’s scripting language.

I used to write quite a bit of JavaScript for web programming but since WASM came along and allows me to run C++ at very nearly full speed inside a web browser, I write almost zero JavaScript these days.

I use C++ for almost everything.

Once you get to know C++ it’s no harder than Python – the main thing I find great about Python is the number of easy-to-find libraries.

But in AAA games – the poor performance of Python pretty much rules it out.

In embedded systems, the computer is generally too small to fit a Python interpreter into memory – so C or C++ is a more likely choice.

Typescript vs JavaScript: Similarities and Differences

 JavaScript is a scripting language, that was developed by EMCA’s Technical Committee and Brendan Eich. It works perfectly in web-browsers without the help of any web-server or a compiler. It allows you to change HTML and CSS in the browsers without a full page reload. That is why it is used to create dynamic and interactive web pages. 

TypeScript is a superset of the JavaScript language. It was presented and developed by Microsoft technical fellow Anders Hejlsberg in 2012. Typescript has appeared for a certain reason: the more JavaScript grew, the heavier and more unreadable js code became. It turned up especially evident when developers started to use JavaScript for server-side technologies.

TypeScript is an open-source language that has a compiler, that converts TypeScript code to JavaScript code (see TypeScript playground service). That compiler is cross-browser and also open-source. To start using TypeScript, you can rename your .js files to .ts files, and if there are no logical mistakes in the js code, you get valid TypeScript code. So, TypeScript code Is JavaScript code (and vice versa) just with some additions. To learn more about those additions, watch the original video presentation of TypeScript. Meanwhile, we discuss the key differences between JS and TS in 2022.   

Why has there not been more take up of TypeScript given its apparent advantages?

I think TypeScript *is* pretty popular, within the constraints it has.

Node.js is 1.8% of websites, and TypeScript is seldom used outside of Node.js. That really means TypeScript has limited potential for use there.

You can use TypeScript on the client-side, but it can be a pain to set up, and unless you have quite a lot of client-side logic, it might not be worth it.

Personally, I think TypeScript on the client-side is well worth the effort, but not really worth it on the server side, where there are so many options outside of a JS runtime.

Why would people say JavaScript is a dead language if it seems like the entire internet runs on JS?

I don’t think anybody says JavaScript is a dead language. I think its long term future is pretty bleak though, for two reasons:

1. TypeScript.
2. WebAssembly.

The entire Internet doesn’t run on JavaScript, in fact hardly any of it does, what you mean is the *web*. The web and the Internet are two different things, and while JavaScript is of course ubiquitous in web sites, practically no Internet infrastructure is using JavaScript.

If you consider the Internet to be the road infrastructure and cars, the web is the screaming babies in the back seats.

Is it a good idea to use TypeScript during software engineering interviews? What are the pros and cons (as opposed to using JavaScript instead)?

 

Unless you can write really good TypeScript code, you’re probably better off sticking to JavaScript – if you have that option of course.

The main advantage of JS vs TS in an interview is that equivalent code will be much quicker to write with JS, as you don’t have to write type annotations and what not. The time that you have to spend mechanically writing code is not negligible and time is off the essence.

Then again, the better you are at TypeScript, the less this will make a difference. Also, in TypeScript there are more ways to write functionally equivalent code, so when you’re really great at TS you’re more susceptible to pick the very best way to express what you want to do, so your expertise and good coding style is more evident. Finally, with good TS you should be able to avoid writing some tests that may be necessary in JS, and your coding style is naturally more defensive, which is good.

If you build a huge website like eBay, Amazon, Facebook today which widely used technology stack and language would you choose: Java/Springboot, C#/.netcore, PHP, Python, Typescript/Reactjs/Node.js (backendMySQL,Linux is mostly fixed)?

 

Originally Answered: If you build a huge website like eBay, Amazon, Facebook today which technology stack and language would you choose: Java/springboot, c#/.netcore, PHP, python, typescript/reactjs/Node.js (backendMySQL,Linux and frontend JavaScript is mostly fixed)?

 

Of those, TypeScript/Node.js/React is an easy answer. Though I’d also strongly recommend TypeScript on the frontend as well. If you skip Redux and instead use React Hooks you should find that TypeScript is a good fit.

But I wouldn’t use MySQL. PostgreSQL is stronger on almost every axis at this point, and given the lack of specificity of the purpose of the web site, I wouldn’t even necessarily recommend PostgreSQL over a half dozen other types of database.

Listen, if you want to design a web site such that it can grow, you need to make key technology choices strategically. If you’re using PostgreSQL, you can nearly seamlessly switch to CockroachDB, for instance, for much easier distributed database performance. Unless your database needs support for Geo-indexing, in which case you might need to split data between CockroachDB and MongoDB (edit: CockroachDB added Geo-index support!). Or if your website would benefit from a graph database, maybe OrientDB would be best.

Designing a website architecture is something that should be done by experienced experts. And the design goes deeper than just the technology choices. You need an architect who knows how to coordinate the architecture and the data flow your specific app will require. Otherwise you could paint yourself into a corner and end up with a site that’s failing at load with no easy path to fixing it, just at the point when your users are asking for more features.

A common cop-out inspired by the agile community is to claim that you just “ignore” the design and optimize later, but the truth is that many services that rely on that approach simply fail when they start to get traction.

Ironically, given your list of companies to be like, Facebook largely succeeded because a previous successful competitor, Friendster, couldn’t keep up with its expansion. The architecture had too many bottlenecks for them to scale horizontally, and they started hemorrhaging users by the thousands when the users found the site to be unresponsive too often. So if you want to be a Facebook, then plan for scaling from the start; otherwise the odds are good you’ll be a Friendster instead.

Not that Facebook necessarily planned it out in advance. I suspect they were instead just lucky. But “being lucky” isn’t a business plan.

What is the best stack for REST API?

A few good ones:

• Java + Spring Boot
• C# .NET
• Node + Express + Typescript
• Go

Can’t go wrong with any of those, really. I personally don’t care too much for the Node solution, but it’s plenty capable (if you can stomach that whole JS ecosystem thing)

What is a simple C++ program to find the average of 2 numbers?

This was actually one of the interview questions I got when I applied at Google.

“Write a function that returns the average of two number.”

So I did, they way you would expect. (x+y)/2. I did it as a C++ template so it works for any kind of number.

interviewer: “What’s wrong with it?”

Well, I suppose there could be an overflow if adding the two numbers requires more than space than the numeric type can hold. So I rewrote it as (x/2) + (y/2).

interviewer: “What’s wrong with it now?”

Well, I think we are losing a little precision by pre-dividing. So I wrote it another way.

interviewer: “What’s wrong with it now?”

And that went on for about 10 minutes. It ended with us talking about the heat death of the universe.

I got the job and ended up working with the guy. He said he had never done that before. He had just wanted to see what would happen.

Comments:

1-

The big problem you get with x/2 + y/2 is that it can/will give incorrect answers for integer inputs. For example, let’s average 3 and 3. The result should obviously be 3.

But with integer division, 3/2 = 1, and 1+1 = 2.

You need to add one to the result if and only if both inputs are odd.

2- Here’s what I’d do in C++ for integers, which I believe does the right thing including getting the rounding direction correct, and it can likely be made into a template that will do the right thing as well. This is not complete code, but I believe it gets the details correct…

That will work for any signed or unsigned integer type for op1 and op2 as long as they have the same type.

If you want it to do something intelligently where one of the operands is an unsigned type and the other one is a signed type, you could do it, but you need to define exactly what should happen, and realize that it’s quite likely that for maximum arithmetic correctness, the output type may need to be different than either input type. For instance, the average of a uint32_t and an int32_t can be too large to fit in an int32_t, and it can also be too small to fit in a uint32_t, so you probably need to go with a larger signed integer type, maybe int64_t.

3- I would have answered the question with a question, “Tell me more about the input, error handling capability of your system, and is this typical of the level of challenge here at google?” Then I’d provide eye contact, sit back, and see what happens. Years ago I had an interview question that asked what classical problem was part of a pen plotter control system. I told the interviewer that it was TSP but that if you had to change pens, you had to consider how much time it took to switch. They offered me a job but I declined given the poor financial condition of the company (SGI) which I discovered by asking the interviewer questions of my own. IMO: questions are at the heart of engineering. The interviewer, if they are smart, wants to see if you are capable of discovering the true nature of their problems. The best programmers I’ve ever worked with were able to get to the heart of problems and trade off solutions. Coding is a small part of the required skills.

Comments:

1- Sorry, but this is just wrong. “Almost all cryptography,” counted by number of bytes encrypted and decrypted, uses AES. AES does not use “large numbers,” elliptic curves, or anything of that sort – it’s essentially combinatorial in nature, with a lot of bit-diddling – though there is some group theory at its based. The same can be said about cryptographic checksums such as the SHA series, including the latest “sponge” constructions.

Where RSA and elliptic curves and such come in is public key cryptography. This is important in setting up connections, but for multiple reasons (performance – but also for excellent cryptographic reasons) is not use for bulk encryption. There are related algorithms like Diffie-Hellman and some signature protocols like DSS. All of these “use large numbers” in some sense, but even that’s pushing it – elliptic curve cryptography involves doing math over … points on an elliptic curve, which does lead you to do some arithmetic, but the big advantage of elliptic curves is that the numbers are way, way smaller than for, say, RSA for equivalent security.

Much research these days is on “post-quantum cryptography” – cryptography that is secure against attacks by quantum computers (assuming we ever make those work). These tend not to be based on “arithmetic” in any straightforward sense – the ones that seem to be at the forefront these days are based on computation over lattices.

Cracking a password database that uses DES is so far away from what cryptography today is about that it’s not even related. Yes, the original Unix implementations – almost 50 years ago – used that approach. So?

Dmitry Aliev is correct that this was introduced into the language before references.

I’ll take this question as an excuse to add a bit more color to this.

C++ evolved from C via an early dialect called “C with Classes”, which was initially implemented with Cpre, a fancy “preprocessor” targeting C that didn’t fully parse the “C with Classes” language. What it did was add an implicit this pointer parameter to member functions. E.g.:

was translated to something like:

• int f__1S(S *this); 

(the funny name f__1S is just an example of a possible “mangling” of the name of S::f, which allows traditional linkers to deal with the richer naming environment of C++).

What might comes as a surprise to the modern C++ programmer is that in that model this is an ordinary parameter variable and therefore it can be assigned to! Indeed, in the early implementations that was possible:

 

Interestingly, an idiom arose around this ability: Constructors could manage class-specific memory allocation by “assigning to this” before doing anything else in the constructor. E.g.:

 

That technique (brittle as it was, particularly when dealing with derived classes) became so widespread that when C with Classes was re-implemented with a “real” compiler (Cfront), assignment to this remained valid in constructors and destructors even though this had otherwise evolved into an immutable expression. The C++ front end I maintain still has modes that accept that anachronism. See also section 17 of the old Cfront manual found here, for some fun reminiscing.

When standardization of C++ began, the core language work was handled by three working groups: Core I dealt with declarative stuff, Core II dealt with expression stuff, and Core III dealt with “new stuff” (templates and exception handling, mostly). In this context, Core II had to (among many other tasks) formalize the rules for overload resolution and the binding of this. Over time, they realized that that name binding should in fact be mostly like reference binding. Hence, in standard C++ the binding of something like:

 

In other words, the expression this is now effectively a kind of alias for &__this, where __this is just a name I made up for an unnamable implicit reference parameter.

C++11 further tweaked this by introducing syntax to control the kind of reference that this is bound from. E.g.,

That model was relatively well-understood by the mid-to-late 1990s… but then unfortunately we forgot about it when we introduced lambda expression. Indeed, in C++11 we allowed lambda expressions to “capture” this:

 

 

After that language feature was released, we started getting many reports of buggy programs that “captured” this thinking they captured the class value, when instead they really wanted to capture __this (or *this). So we scrambled to try to rectify that in C++17, but because lambdas had gotten tremendously popular we had to make a compromise. Specifically:

• we introduced the ability to capture *this
• we allowed [=, this] since now [this] is really a “by reference” capture of *this
• even though [this] was now a “by reference” capture, we left in the ability to write [&, this], despite it being redundant (compatibility with earlier standards)

Our tale is not done, however. Once you write much generic C++ code you’ll probably find out that it’s really frustrating that the __this parameter cannot be made generic because it’s implicitly declared. So we (the C++ standardization committee) decided to allow that parameter to be made explicit in C++23. For example, you can write (example from the linked paper):

In that example, the “object parameter” (i.e., the previously hidden reference parameter __this) is now an explicit parameter and it is no longer a reference!

Here is another example (also from the paper):

 

Here:

• the type of the object parameter is a deducible template-dependent type
• the deduction actually allows a derived type to be found

This feature is tremendously powerful, and may well be the most significant addition by C++23 to the core language. If you’re reasonably well-versed in modern C++, I highly recommend reading that paper (P0847) — it’s fairly accessible.

Does the use of REST API make development slow versus not using REST API?

It adds some extra steps in design, testing and deployment for sure. But it can buy you an easier path to scalability and an easier path to fault tolerance and live system upgrades.

It’s not REST itself that enables that. But if you use REST you will have split your code up into independently deployable chunks called services.

So more development work to do, yes, but you get something a single monolith can’t provide. If you need that, then the REST service approach is a quick way to doing it.

We must compare like for like in terms of results for questions like this.

Why didn’t the C library designers make strtok() explicitly store the state to allow working on multiple strings at the same time?

 

Because at the time, there was likely no need.

Based on what I could find, the strtok library function appeared in System III UNIX some time in 1980.

In 1980, memory was small, and programs were single threaded. I don’t know whether UNIX had any support for multiple processors, even. I think that happened a few years later.

Its implementation was quite simple.

 

This was 3 years before they started the standardization process, and 9 years before it was standardized in ANSI C.

This was simple and good enough, and that’s what mattered most. It’s far from the only library function with internal state.

And Lex/YACC took over more complex scanning and parsing tasks, so it probably didn’t get a lot of attention for the lightweight uses it was put to.

For a tongue-in-cheek take on how UNIX and C were developed, read this classic:

 

The Rise of “Worse is Better” By Richard Gabriel I and just about every designer of Common Lisp and CLOS has had extreme exposure to the MIT/Stanford style of design. The essence of this style can be captured by the phrase “the right thing.” To such a designer it is important to get all of the following characteristics right: · Simplicity-the design must be simple, both in implementation and interface. It is more important for the interface to be simple than the implementation. · Correctness-the design must be correct in all observable aspects. Incorrectness is simply not allowed. · Consistency-the design must not be inconsistent. A design is allowed to be slightly less simple and less complete to avoid inconsistency. Consistency is as important as correctness. · Completeness-the design must cover as many important situations as is practical. All reasonably expected cases must be covered. Simplicity is not allowed to overly reduce completeness. I believe most people would agree that these are good characteristics. I will call the use of this philosophy of design the “MIT approach.” Common Lisp (with CLOS) and Scheme represent the MIT approach to design and implementation. The worse-is-better philosophy is only slightly different: · Simplicity-the design must be simple, both in implementation and interface. It is more important for the implementation to be simple than the interface. Simplicity is the most important consideration in a design. · Correctness-the design must be correct in all observable aspects. It is slightly better to be simple than correct. · Consistency-the design must not be overly inconsistent. Consistency can be sacrificed for simplicity in some cases, but it is better to drop those parts of the design that deal with less common circumstances than to introduce either implementational complexity or inconsistency. · Completeness-the design must cover as many important situations as is practical. All reasonably expected cases should be covered. Completeness can be sacrificed in favor of any other quality. In fact, completeness must sacrificed whenever implementation simplicity is jeopardized. Consistency can be sacrificed to achieve completeness if simplicity is retained; especially worthless is consistency of interface. Early Unix and C are examples of the use of this school of design, and I will call the use of this design strategy the “New Jersey approach.” I have intentionally caricatured the worse-is-better philosophy to convince you that it is obviously a bad philosophy and that the New Jersey approach is a bad approach. However, I believe that worse-is-better, even in its strawman form, has better survival characteristics than the-right-thing, and that the New Jersey approach when used for software is a better approach than the MIT approach. Let me start out by retelling a story that shows that the MIT/New-Jersey distinction is valid and that proponents of each philosophy actually believe their philosophy is better.

https://web.stanford.edu/class/cs240/old/sp2014/readings/worse-is-better.html

 

 

Because the ‘under the hood’ code is about 50 years old. I’m not kidding. I worked on some video poker machines that were made in the early 1970’s.

Here’s how they work.

You have an array of ‘cards’ from 0 to 51. Pick one at random. Slap it in position 1 and take it out of your array. Do the same for the next card … see how this works?

Video poker machines are really that simple. They literally simulate a deck of cards.

Anything else, at least in Nevada, is illegal. Let me rephrase that, it is ILLEGAL, in all caps.

If you were to try to make a video poker game (or video keno, or slot machine) in any other way than as close to truly random selection from an ‘array’ of options as you can get, Nevada Gaming will come after you so hard and fast, your third cousin twice removed will have their ears ring for a week.

That is if the Families don’t get you first, and they’re far less kind.

All the ‘magic’ is in the payout tables, which on video poker and keno are literally posted on every machine. If you can read them, you can figure out exactly what the payout odds are for any machine.

There’s also a little note at the bottom stating that the video poker machine you’re looking at uses a 52 card deck.

Comments:

1- I have a slot machine and the code on the odds chip looks much like an excel spread sheet every combination is displayed in this spread sheet, so the exact odds can be listed an payout tables. The machine picks a random number. Let say 452 in 1000. the computer looks at the spread sheet and says that this is the combination of bar bar 7 and you get 2 credits for this combination. The wheels will spin to match the indication on the spread sheet. If I go into the game diagnostics I can see if it is a win or not, you do not win on what the wheels display, but the actual number from the spread sheet. The games knows if you won or lost before the wheels stop.

2- I had a conversation with a guy who had retired from working in casino security. He was also responsible for some setup and maintenance on slot machines, video poker and others. I asked about the infamous video poker machine that a programmer at the manufacturer had put in a backdoor so he and a few pals could get money. That was just before he’d started but he knew how it was done. IIRC there was a 25 step process of combinations of coin drops and button presses to make the machine hit a royal flush to pay the jackpot.

Slot machines that have mechanical reels actually run very large virtual reels. The physical reels have position encoders so the electronics and software can select which symbol to stop on. This makes for far more possible combinations than relying on the space available on the physical reels.

Those islands of machines with the sign that says 95% payout? Well, you guess which machine in the group is set to that payout % while the rest are much closer to the minimum allowed.

Machines with a video screen that gives you a choice of things to select by touch or button press? It doesn’t matter what you select, the outcome is pre-determined. For example, if there’s a grid of spots and the first three matches you get determines how many free spins you get, if the code stopped on giving you 7 free spins, out of a possible maximum of 25, you’re getting 7 free spins no matter which spots you touch. It will tease you with a couple of 25s, a 10 or 15 or two, but ultimately you’ll get three 7s, and often the 3rd 25 will be close to the other two or right next to the last 7 “you” selected to make you feel like you just missed it when the full grid is briefly revealed.

There was a Discovery Channel show where the host used various power tools to literally hack things apart to show their insides and how they worked. In one episode he sawed open a couple of slot machines, one from the 1960’s and a purely mechanical one from the 1930’s or possibly 1940’s. In that old machine he discovered the casino it had been in decades prior had installed a cheat. There was a metal wedge bolted into the notch for the 7 on one reel so it could never hit the 777 jackpot. I wondered if the Nevada Gaming Commission could trace the serial number and if they could levy a fine if the company that had owned and operated it was still in business.

3- Slightly off-topic. I worked for a company that sold computer hardware, one of our customers was the company that makes gambling machines. They said that they spent close to $0 on software and all their budget on licensing characters

Why would you ever use an array when you can just use an ArrayList in Java?

 

This question is like asking why you would ever use int when you have the Integer class. Java programmers seem especially zealous about everything needing to be wrapped, and wrapped, and wrapped.

Yes, ArrayList<Integer> does everything that int[] does and more… but sometimes all you need to do is swat a fly, and you just need a flyswatter, not a machine-gun.

Did you know that in order to convert int[] to ArrrayList<Integer>, the system has to go through the array elements one at a time and box them, which means creating a garbage-collected object on the heap (i.e. Integer) for each individual int in the array? That’s right; if you just use int[], then only one memory alloc is needed, as opposed to one for each item.

I understand that most Java programmers don’t know about that, and the ones who do probably don’t care. They will say that this isn’t going to be the reason your program is running slowly. They will say that if you need to care about those kinds of optimizations, then you should be writing code in C++ rather than Java. Yadda yadda yadda, I’ve heard it all before. Personally though, I think that you should know, and should care, because it just seems wasteful to me. Why dynamically allocate n individual objects when you could just have a contiguous block in memory? I don’t like waste.

I also happen to know that if you have a blasé attitude about performance in general, then you’re apt to be the sort of programmer who unknowingly, unnecessarily writes four nested loops and then has no idea why their program took ten minutes to run even though the list was only 100 elements long. At that point, not even C++ will save you from your inefficiently written code. There’s a slippery slope here.

I believe that a software developer is a sort of craftsman. They should understand their craft, not only at the language level, but also how it works internally. They should convert int[] to ArrayList<Integer> only because they know the cost is insignificant, and they have a particular reason for doing so other than “I never use arrays, ArrayList is better LOL”.

Are object-oriented programming concepts the same in C# and Java?

Very similar, yes.

Both languages feature:

• Static typing
• nominative interface typing
• garbage collection
• class based
• single dispatch polymorphism

so whilst syntax differs, the key things that separate OO support across languages are the same.

There are differences but you can write the same design of OO program in either language and it won’t look out of place

Java or Kotlin in 2022? Whats easier and better for Android app developing ?

Last time I needed to write an Android app, even though I already knew Java, I still went with Kotlin 😀

I’d rather work in a language I don’t know than… Java… and yes, I know a decent Java IDE can auto-generate this code – but this only solves the problem of writing the code, it doesn’t solve the problem of having to read it, which happens a lot more than writing it.

I mean, which of the below conveys the programmer’s intent more clearly, and which one would you rather read when you forget what a part of the program does and need a refresher:

Even if both of them required no effort to write… the Java version is pure brain poison…

What’s the general truth you’ve discovered behind the dozens of tech/programming books you’ve read?

If you have two books on the same subject, but one is skinny and the other is fat, go with the skinny one. For example:

The book on the left has 796 pages; the book on the right a mere 176. Yet the book on the right told us everything we needed to know to write our own, efficient, native-code-generating Plain English compiler in Plain English:

 

 

The Osmosian Order of Plain English Programmers Welcomes You

Program in a language you already know

https://osmosianplainenglishprogramming.blog/

 

Compare also the Inside Macintosh documentation before and after the Pascal programmers were replaced with C programmers:

Note that the whole set (green arrow) documenting the slim and trim Pascal system was the same size as a single volume (red arrow) of the bloated C version.

Et voila!

Why is volatile not considered useful in multithreaded C or C++ programming?

Because it’s insufficient to deal with the memory semantics of current computers. In fact, it was obsolete almost as soon as it first became available.

Volatile tells a compiler that it may not assume the value of a memory location has not changed between reads or writes. This is sometimes sufficient to deal with memory-mapped hardware registers, which is what it was originally for.

But that doesn’t deal with the semantics of a multiprocessor machine’s cache, where a memory location might be written and read from several different places, and we need to be sure we know when written values will be observable relative to control flow in the writing thread.

Instead, we need to deal with acquire/release semantics of values, and the compilers have to output the right machine instructions that we get those semantics from the real machines. So, the atomic memory intrinsics come to the rescue. This is also why inline assembler acts as an optimization barrier; before there were intrinsics for this, it was done with inline assembler. But intrinsics are better, because the compiler can still do some optimization with them.

Why isn’t C++ designed to detect undefined behaviour runtime?

C++ is a programming language specified through a standard that is “abstract” in various ways. For example, that standard doesn’t currently formally recognize a notion of “runtime” (I would actually like to change that a little bit in the future, but we’ll see).

Now, in order to allow implementations to make assumptions it removes certain situations from the responsibility of the implementation. For example, it doesn’t require (in general) that the implementation ensure that accesses to objects are within the bounds of those objects. By dropping that requirement, the code for valid accesses can be more efficient than would be required if out-of-bounds situations were the responsibility of the implementation (as is the case in most other modern programming languages). Those “situations” are what we call “undefined behaviour”: The implementation has no specific responsibilities and so the standard allows “anything” to happen. This is in part why C++ is still very successful in applications that call for the efficient use of hardware resources.

Note, however, that the standard doesn’t disallow an implementation from doing something that is implementation-specified in those “undefined behaviour” situations. It’s perfectly all right (and feasible) for a C++ implementation to be “memory safe” for example (e.g., not attempt access outside of object bounds). Such implementations have existed in the past (and might still exist, but I’m not currently aware of one that completely “contains” undefined behaviour).

ADDENDUM (July 16th, 2021):

The following article about undefined behavior crossed my metaphorical desk today:

 

Schrödinger’s Code

May 26, 2021 Volume 19, issue 2 PDF Drill Bits Schrödinger’s Code Undefined behavior in theory and practice Terence Kelly with special guest borers Weiwei Gu and Vladimir Maksimovski Sanity vs. Speed Undefined behavior ranks among the most baffling and perilous aspects of popular programming languages. This installment of Drill Bits clears up widespread misconceptions and presents practical techniques to banish undefined behavior from your own code and pinpoint meaningless operations in any software—techniques that reveal alarming faults in software supporting business-critical applications at Fortune 500 companies. Early in the history of programming languages, two schools of thought diverged. Quicksort inventor C.A.R. Hoare summarized one philosophy in his Turing Award lecture: 7 The behavior of every syntactically correct program should be completely predictable from its source code. For the sake of safety, security, and programmer sanity, it must be impossible for a program to “run wild.” Ensuring well-defined behavior imposes runtime overheads (e.g., array bounds checks), but predictability justifies the cost. Today, “safe” languages such as Java embody Hoare’s advice. A different philosophy reigns in domains that demand efficiency and speed (e.g., infrastructure software). Systems programming languages such as C and C++ sacrifice safety and comprehensive semantics for performance. These languages, despite being meticulously standardized, do not define the behavior of all code that compiles. If a running program violates any one of myriad rules, all bets are off. The program might behave as intended, or crash, or corrupt priceless data, or serve an Internet villain. The computer might even catch fire—rogue software could literally fry the original IBM PC. 13 By declaring that certain coding errors yield undefined behavior, language standards permit compilers to skip runtime checks and optimize aggressively. They also shift the burden of ensuring predictability onto the programmer. Unfortunately, undefined behavior arises in many ways; appendix J.2 of the C standard lists scores, 2 and C++ adds many more. 3 This article surveys the most prominent pitfalls, presents examples from production software, and suggests practical ways to prevent and detect such bugs in serial code. An earlier Queue article by Hans-J. Boehm and Sarita V. Adve discusses undefined behavior in multithreaded software. 1 Guesswork Physical intuition misleads some developers into believing they can predict the behavior of software that executes undefined operations: “If defective track derails a locomotive, the train will go somewhere ,” they reason, concluding that we can know where. If pure reasoning can’t deduce the outcome, surely experiment must be definitive: “Like Schrödinger’s cat, undefined software exists in an indeterminate state only until we observe its behavior, whereupon something will happen.” Try it and see, says this mentality….