Best questions in March 2014

Why should I use a pointer rather than the object itself?

546 votes

I'm coming from a Java background and have started working with objects in C++. But one thing that occurred to me is that people often use pointers to objects rather than the objects themselves, for example this declaration:

Object *myObject = new Object;

rather than:

Object myObject;

Or instead of using a function, let's say testFunc(), like this:

myObject.testFunc();

we have to write:

myObject->testFunc();

But I can't figure out why should we do it this way. I would assume it has to do with efficiency and speed since we get direct access to the memory address. Am I right?

It's very unfortunate that you see dynamic allocation so often. That just shows how many bad C++ programmers there are.

In a sense, you have two questions bundled up into one. The first is when should we use dynamic allocation (using new)? The second is when should we use pointers?

The important take-home message is that you should always use the appropriate tool for the job. In almost all situations, there is something more appropriate and safer than performing manual dynamic allocation and/or using raw pointers.

Dynamic allocation

In your question, you've demonstrated two ways of creating an object. The main difference is the storage duration of the object. When doing Object myObject; within a block, the object is created with automatic storage duration, which means it will be destroyed automatically when it goes out of scope. When you do new Object(), the object has dynamic storage duration, which means it stays alive until you explicitly delete it. You should only use dynamic storage duration when you need it. That is, you should always prefer creating objects with automatic storage duration when you can.

The main two situations in which you might require dynamic allocation:

  1. You need the object to outlive the current scope - that specific object at that specific memory location, not a copy of it. If you're okay with copying/moving the object (most of the time you should be), you should prefer an automatic object.
  2. You need to allocate a lot of memory, which may easily fill up the stack. It would be nice if we didn't have to concern ourselves with this (most of the time you shouldn't have to), as it's really outside the purview of C++, but unfortunately we have to deal with the reality of the systems we're developing for.

When you do absolutely require dynamic allocation, you should encapsulate it in a smart pointer or some other type that performs RAII (like the standard containers). Smart pointers provide ownership semantics of dynamically allocated objects. Take a look at std::unique_ptr and std::shared_ptr, for example. If you use them appropriately, you can almost entirely avoid performing your own memory management (see the Rule of Zero).

Pointers

However, there are other more general uses for raw pointers beyond dynamic allocation, but most have alternatives that you should prefer. As before, always prefer the alternatives unless you really need pointers.

  1. You need reference semantics. Sometimes you want to pass an object using a pointer (regardless of how it was allocated) because you want the function to which you're passing it to have access that that specific object (not a copy of it). However, in most situations, you should prefer reference types to pointers, because this is specifically what they're designed for. Note this is not necessarily about extending the lifetime of the object beyond the current scope, as in situation 1 above. As before, if you're okay with passing a copy of the object, you don't need reference semantics.

  2. You need polymorphism. You can only call functions polymorphically (that is, according to the dynamic type of an object) through a pointer or reference to the object. If that's the behaviour you need, then you need to use pointers or references. Again, references should be preferred.

  3. You want to represent that an object is optional by allowing a nullptr to be passed when the object is being omitted. If it's an argument, you should prefer to use default arguments or function overloads. Otherwise, you should prefer use a type that encapsulates this behaviour, such as boost::optional (or perhaps soon, std::optional - Edit std::optional is voted out of the current C++14 draft n3797).

  4. You want to decouple compilation units to improve compilation time. The useful property of a pointer is that you only require a forward declaration of the pointed-to type (to actually use the object, you'll need a definition). This allows you to decouple parts of your compilation process, which may significantly improve compilation time. See the Pimpl idiom.

  5. You need to interface with a C library or a C-style library. At this point, you're forced to use raw pointers. The best thing you can do is make sure you only let your raw pointers loose at the last possible moment. You can get a raw pointer from a smart pointer, for example, by using its get member function. If a library performs some allocation for you which it expects you to deallocate via a handle, you can often wrap the handle up in a smart pointer with a custom deleter that will deallocate the object appropriately.

What does the constant 0.0039215689 represent?

204 votes

I keep seeing this constant pop up in various graphics header files

0.0039215689

It seems to have something to do with color maybe?

Here is the first hit on Google:

void RDP_G_SETFOGCOLOR(void)
{
    Gfx.FogColor.R = _SHIFTR(w1, 24, 8) * 0.0039215689f;
    Gfx.FogColor.G = _SHIFTR(w1, 16, 8) * 0.0039215689f;
    Gfx.FogColor.B = _SHIFTR(w1, 8, 8) * 0.0039215689f;
    Gfx.FogColor.A = _SHIFTR(w1, 0, 8) * 0.0039215689f;
}

void RDP_G_SETBLENDCOLOR(void)
{
    Gfx.BlendColor.R = _SHIFTR(w1, 24, 8) * 0.0039215689f;
    Gfx.BlendColor.G = _SHIFTR(w1, 16, 8) * 0.0039215689f;
    Gfx.BlendColor.B = _SHIFTR(w1, 8, 8) * 0.0039215689f;
    Gfx.BlendColor.A = _SHIFTR(w1, 0, 8) * 0.0039215689f;

    if(OpenGL.Ext_FragmentProgram && (System.Options & BRDP_COMBINER)) {
        glProgramEnvParameter4fARB(GL_FRAGMENT_PROGRAM_ARB, 2, Gfx.BlendColor.R, Gfx.BlendColor.G, Gfx.BlendColor.B, Gfx.BlendColor.A);
    }
}

//...more like this

What does this number represent? Why does no one seem to declare it as a const?

I couldn't find anything on Google that explained it.

0.0039215689 is approximately equal to 1/255.

Seeing that this is OpenGL, performance is probably important. So it's probably safe to guess that this was done for performance reasons.

Multiplying by the reciprocal is faster than repeatedly dividing by 255.


Side Note:

If you're wondering why such a micro-optimization isn't left to the compiler, it's because it is an unsafe floating-point optimization. In other words:

x / 255  !=  x * (1. / 255)

due to floating-point round-off errors.

So while modern compilers may be smart enough to do this optimization, they are not allowed to do it unless you explicitly tell them to via a compiler flag.

Related: Why doesn't GCC optimize a*a*a*a*a*a to (a*a*a)*(a*a*a)?

Too many 'if' statements?

194 votes

The following code does work how I need it to, but it's ugly, excessive or a number of other things. I've looked at formulas and attempted to write a few solutions, but I end up with a similar amount of statements.

Is there a type of math formula that would benefit me in this instance or are 16 if statements acceptable?

To explain the code, it's for a kind of simultaneous-turn-based game.. two players have four action buttons each and the results come from an array (0-3), but the variables 'one' & 'two' can be assigned anything if this helps. The result is, 0 = neither win, 1 = p1 wins, 2 = p2 wins, 3 = both win.

public int fightMath(int one, int two) {

    if(one == 0 && two == 0) { result = 0; }
    else if(one == 0 && two == 1) { result = 0; }
    else if(one == 0 && two == 2) { result = 1; }
    else if(one == 0 && two == 3) { result = 2; }
    else if(one == 1 && two == 0) { result = 0; }
    else if(one == 1 && two == 1) { result = 0; }
    else if(one == 1 && two == 2) { result = 2; }
    else if(one == 1 && two == 3) { result = 1; }
    else if(one == 2 && two == 0) { result = 2; }
    else if(one == 2 && two == 1) { result = 1; }
    else if(one == 2 && two == 2) { result = 3; }
    else if(one == 2 && two == 3) { result = 3; }
    else if(one == 3 && two == 0) { result = 1; }
    else if(one == 3 && two == 1) { result = 2; }
    else if(one == 3 && two == 2) { result = 3; }
    else if(one == 3 && two == 3) { result = 3; }

    return result;
}

If you cannot come up with a formula, you can use a table for such a limited number of outcomes:

final int[][] result = new int[][] {
  { 0, 0, 1, 2 },
  { 0, 0, 2, 1 },
  { 2, 1, 3, 3 },
  { 1, 2, 3, 3 }
};
return result[one][two];

What actually causes a Stack Overflow error?

158 votes

I've looked everywhere and can't find a solid answer. According to the documentation, Java throws a java.lang.StackOverflowError error under the following circumstance:

Thrown when a stack overflow occurs because an application recurses too deeply.

But this raises two questions:

  • Aren't there other ways for a stack overflow to occur, not only through recursion?
  • Does the StackOverflowError happen before the JVM actually overflows the stack or after?

To elaborate on the second question:

When Java throws the StackOverflowError, can you safely assume that the stack did not write into the heap? If you shrink the size of the stack or heap in a try/catch on a function that throws a stack overflow, can you continue working? Is this documented anywhere?

Answers I am not looking for:

  • A StackOverflow happens because of bad recursion.
  • A StackOverflow happens when the heap meets the stack.

It seems you're thinking that a stackoverflow error is like a buffer overflow exception in native programs, when there is a risk of writing into memory that had not been allocated for the buffer, and thus to corrupt some other memory locations. It's not the case at all.

JVM has a given memory allocated for each stack of each thread, and if an attempt to call a method happens to fill this memory, JVM throws an error. Just like it would do if you were trying to write at index N of an array of length N. No memory corruption can happen. The stack can not write into the heap.

A StackOverflowError is to the stack what an OutOfMemoryError is to the heap: it simply signals that there is no more memory available.

Description from Virtual Machine Errors (§6.3)

StackOverflowError: The Java Virtual Machine implementation has run out of stack space for a thread, typically because the thread is doing an unbounded number of recursive invocations as a result of a fault in the executing program.

clang error: unknown argument: '-mno-fused-madd' (python package installation failure)

93 votes

I get the following error when attempting to install psycopg2 via pip on Mavericks 10.9:

clang: error: unknown argument: '-mno-fused-madd' [-Wunused-command-line-argument-hard-error-in-future]

Not sure how to proceed and have searched here and elsewhere for this particular error. Any help is much appreciated!

Here is the complete output from pip:

$ pip install psycopg2
Downloading/unpacking psycopg2
  Downloading psycopg2-2.5.2.tar.gz (685kB): 685kB downloaded
  Running setup.py (path:/private/var/folders/0z/ljjwsjmn4v9_zwm81vhxj69m0000gn/T/pip_build_tino/psycopg2/setup.py) egg_info for package psycopg2

Installing collected packages: psycopg2
  Running setup.py install for psycopg2
    building 'psycopg2._psycopg' extension
    cc -fno-strict-aliasing -fno-common -dynamic -arch x86_64 -arch i386 -g -Os -pipe -fno-common -fno-strict-aliasing -fwrapv -mno-fused-madd -DENABLE_DTRACE -DMACOSX -DNDEBUG -Wall -Wstrict-prototypes -Wshorten-64-to-32 -DNDEBUG -g -fwrapv -Os -Wall -Wstrict-prototypes -DENABLE_DTRACE -arch x86_64 -arch i386 -pipe -DPSYCOPG_DEFAULT_PYDATETIME=1 -DPSYCOPG_VERSION="2.5.2 (dt dec pq3 ext)" -DPG_VERSION_HEX=0x090303 -DPSYCOPG_EXTENSIONS=1 -DPSYCOPG_NEW_BOOLEAN=1 -DHAVE_PQFREEMEM=1 -I/System/Library/Frameworks/Python.framework/Versions/2.7/include/python2.7 -I. -I/usr/local/Cellar/postgresql/9.3.3/include -I/usr/local/Cellar/postgresql/9.3.3/include/server -c psycopg/psycopgmodule.c -o build/temp.macosx-10.9-intel-2.7/psycopg/psycopgmodule.o
    clang: error: unknown argument: '-mno-fused-madd' [-Wunused-command-line-argument-hard-error-in-future]
    clang: note: this will be a hard error (cannot be downgraded to a warning) in the future
    error: command 'cc' failed with exit status 1
    Complete output from command /usr/bin/python -c "import setuptools, tokenize;__file__='/private/var/folders/0z/ljjwsjmn4v9_zwm81vhxj69m0000gn/T/pip_build_tino/psycopg2/setup.py';exec(compile(getattr(tokenize, 'open', open)(__file__).read().replace('\r\n', '\n'), __file__, 'exec'))" install --record /var/folders/0z/ljjwsjmn4v9_zwm81vhxj69m0000gn/T/pip-bnWiwB-record/install-record.txt --single-version-externally-managed --compile:
    running install

running build

running build_py

creating build

creating build/lib.macosx-10.9-intel-2.7

creating build/lib.macosx-10.9-intel-2.7/psycopg2

copying lib/__init__.py -> build/lib.macosx-10.9-intel-2.7/psycopg2

copying lib/_json.py -> build/lib.macosx-10.9-intel-2.7/psycopg2

copying lib/_range.py -> build/lib.macosx-10.9-intel-2.7/psycopg2

copying lib/errorcodes.py -> build/lib.macosx-10.9-intel-2.7/psycopg2

copying lib/extensions.py -> build/lib.macosx-10.9-intel-2.7/psycopg2

copying lib/extras.py -> build/lib.macosx-10.9-intel-2.7/psycopg2

copying lib/pool.py -> build/lib.macosx-10.9-intel-2.7/psycopg2

copying lib/psycopg1.py -> build/lib.macosx-10.9-intel-2.7/psycopg2

copying lib/tz.py -> build/lib.macosx-10.9-intel-2.7/psycopg2

creating build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/__init__.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/dbapi20.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/dbapi20_tpc.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/test_async.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/test_bug_gc.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/test_bugX000.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/test_cancel.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/test_connection.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/test_copy.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/test_cursor.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/test_dates.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/test_extras_dictcursor.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/test_green.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/test_lobject.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/test_module.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/test_notify.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/test_psycopg2_dbapi20.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/test_quote.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/test_transaction.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/test_types_basic.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/test_types_extras.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/test_with.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/testconfig.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

copying tests/testutils.py -> build/lib.macosx-10.9-intel-2.7/psycopg2/tests

running build_ext

building 'psycopg2._psycopg' extension

creating build/temp.macosx-10.9-intel-2.7

creating build/temp.macosx-10.9-intel-2.7/psycopg

cc -fno-strict-aliasing -fno-common -dynamic -arch x86_64 -arch i386 -g -Os -pipe -fno-common -fno-strict-aliasing -fwrapv -mno-fused-madd -DENABLE_DTRACE -DMACOSX -DNDEBUG -Wall -Wstrict-prototypes -Wshorten-64-to-32 -DNDEBUG -g -fwrapv -Os -Wall -Wstrict-prototypes -DENABLE_DTRACE -arch x86_64 -arch i386 -pipe -DPSYCOPG_DEFAULT_PYDATETIME=1 -DPSYCOPG_VERSION="2.5.2 (dt dec pq3 ext)" -DPG_VERSION_HEX=0x090303 -DPSYCOPG_EXTENSIONS=1 -DPSYCOPG_NEW_BOOLEAN=1 -DHAVE_PQFREEMEM=1 -I/System/Library/Frameworks/Python.framework/Versions/2.7/include/python2.7 -I. -I/usr/local/Cellar/postgresql/9.3.3/include -I/usr/local/Cellar/postgresql/9.3.3/include/server -c psycopg/psycopgmodule.c -o build/temp.macosx-10.9-intel-2.7/psycopg/psycopgmodule.o

clang: error: unknown argument: '-mno-fused-madd' [-Wunused-command-line-argument-hard-error-in-future]

clang: note: this will be a hard error (cannot be downgraded to a warning) in the future

error: command 'cc' failed with exit status 1

----------------------------------------
Cleaning up...
Command /usr/bin/python -c "import setuptools, tokenize;__file__='/private/var/folders/0z/ljjwsjmn4v9_zwm81vhxj69m0000gn/T/pip_build_tino/psycopg2/setup.py';exec(compile(getattr(tokenize, 'open', open)(__file__).read().replace('\r\n', '\n'), __file__, 'exec'))" install --record /var/folders/0z/ljjwsjmn4v9_zwm81vhxj69m0000gn/T/pip-bnWiwB-record/install-record.txt --single-version-externally-managed --compile failed with error code 1 in /private/var/folders/0z/ljjwsjmn4v9_zwm81vhxj69m0000gn/T/pip_build_tino/psycopg2

You can tell clang to not raise this as an error by setting the following environment variables prior compilation:

export CFLAGS=-Qunused-arguments
export CPPFLAGS=-Qunused-arguments

Then pip install psycopg2should work.

I had the same when trying to pip install lxml.

Edit: if you are installing as superuser (which will likely be the case if you are trying to append to /Library/Python/2.7/site-packages, the native Apple factory-installed Python distribution which ships with OS X, rather than to some other Python distribution which you have subsequently installed yourself), then you will need to do, as described by @Thijs Kuipers in comments below:

sudo -E pip install psycopg2

or the equivalent, for whatever other package name you may be substituting in place of psycopg2.

Do I have to guard against SQL injection if I used a dropdown?

83 votes

I understand that you should NEVER trust user input from a form, mainly due to the chance of SQL injection.

However, does this also apply to a form where the only input is from a dropdown(s) (see below)?

I'm saving the $_POST['size'] to a Session which is then used throughout the site to query the various databases (with a mysqli Select query) and any SQL injection would definitely harm (possibly drop) them.

There is no area for typed user input to query the databases, only dropdown(s).

<form action="welcome.php" method="post">
<select name="size">
  <option value="All">Select Size</option> 
  <option value="Large">Large</option>
  <option value="Medium">Medium</option>
  <option value="Small">Small</option>
</select>
<input type="submit">
</form>

You could do something as simple as the following example to make sure the posted size is what you expect.

$possibleOptions = array('All', 'Large', 'Medium', 'Small');

if(in_array($_POST['size'], $possibleOptions)) {
    // Expected
} else {
    // Not Expected
}

Then use mysqli_* if you are using a version of php >= 5.3.0 which you should be, to save your result. If used correctly this will help with sql injection.

Console.WriteLine() and the need for so many argument overloads?

Asked on Fri, 07 Mar 2014 by B.K. c#
81 votes

So, I was just browsing through documentation and noticed that Console.WriteLine() method had several overloads. Particularly, my curiosity and partial confusion pertains to these:

public static void WriteLine(string format, params object[] arg);
public static void WriteLine(string format, object arg0);
public static void WriteLine(string format, object arg0, object arg1);
public static void WriteLine(string format, object arg0, object arg1, object arg2);
public static void WriteLine(string format, object arg0, object arg1, object arg2, object arg3);

It seems redundant. What is the need of the other four overloads on top of the first one? The first method is able to do everything that the other methods can do. Is there a performance concern that they were trying to tackle by providing additional overloads, which handle up to four arguments (last one)? Is the overhead of going through an array of up to four arguments large enough to provide the need for these overloads?

In general you are correct that the first overload can suffice for the other overloads. This is not strictly true though because the params keyword can't be used for indirect cases like method group binding. For example

delegate void E(string format, object o1);
E e = Console.WriteLine;

The params overload won't satisfy this case, it will only work when this particular overload is present

public static void WriteLine(string format, object arg0);

That's a pretty esoteric case though. The more important reasons are the following

  1. Not every CLI language is required to support the params keyword. Having the overloads reduces the burden on those languages by removing the need to manually create an array for a simple WriteLine` call
  2. Performance. Calling the params overload forces the caller to allocate an array, even if it's done implicitly by the compiler. Allocations are cheap in .Net but not free. Little things like this add up quickly especially on commonly called methods like Console.WriteLine. Having the other overloads allows for the common cases to avoid this allocation

Is it ever OK to *not* use free() on allocated memory?

81 votes

I'm studying computer engineering, and I have some electronics courses. I heard, from two of my professors (of these courses) that it is possible to avoid using the free() function (after malloc(), calloc(), etc.) because the memory spaces allocated likely won't be used again to allocate other memory. That is, for example, if you allocate 4 bytes and then release them you will have 4 bytes of space that likely won't be allocated again: you will have a hole.

I think that's crazy: you can't have a not-toy-program where you allocate memory on the heap without releasing it. But I don't have the knowledge to explain exactly why it's so important that for each malloc() there must be a free().

So: are there ever circumstances in which it might be appropriate to use a malloc() without using free()? And if not, how can I explain this to my professors?

Easy: just read the source of pretty much any half-serious malloc()/free() implementation. By this, I mean the actual memory manager that handles the work of the calls. This might be in the runtime library, virtual machine, or operating system. Of course the code is not equally accessible in all cases.

Making sure memory is not fragmented, by joining adjacent holes into larger holes, is very very common. More serious allocators use more serious techniques to ensure this.

So, let's assume you do three allocations and de-allocations and get blocks layed out in memory in this order:

+-+-+-+
|A|B|C|
+-+-+-+

The sizes of the individual allocations don't matter. then you free the first and last one, A and C:

+-+-+-+
| |B| |
+-+-+-+

when you finally free B, you (initially, at least in theory) end up with:

+-+-+-+
| | | |
+-+-+-+

which can be de-fragmented into just

+-+-+-+
|     |
+-+-+-+

i.e. a single larger free block, no fragments left.

References, as requested:

Why is it possible to recover from a StackOverflowError?

80 votes

I'm surprised at how it is possible to continue execution even after a StackOverflowError has occurred in Java.

I know that StackOverflowError is a sublass of the class Error. The class Error is decumented as "a subclass of Throwable that indicates serious problems that a reasonable application should not try to catch."

This sounds more like a recommendation than a rule, subtending that catching a Error like a StackOverflowError is in fact permitted and it's up to the programmer's reasonability not to do so. And see, I tested this code and it terminates normally.

public class Test
{
    public static void main(String[] args)
    {
        try {
            foo();
        } catch (StackOverflowError e) {
            bar();
        }
        System.out.println("normal termination");
    }

    private static void foo() {
        System.out.println("foo");
        foo();
    }

    private static void bar() {
        System.out.println("bar");
    }
}

How can this be? I think by the time the StackOverflowError is thrown, the stack should be so full that there is no room for calling another function. Is the error handling block running in a different stack, or what is going on here?

When the stack overflows and StackOverflowError is thrown, the usual exception handling unwinds the stack. Unwinding the stack means:

  • abort the execution of the currently active function
  • delete its stack frame, proceed with the calling function
  • abort the execution of the caller
  • delete its stack frame, proceed with the calling function
  • and so on...

... until the exception is caught. This is normal (in fact, necessary) and independent of which exception is thrown and why. Since you catch the exception outside of the first call to foo(), the thousands of foo stack frames that filled the stack have all been unwound and most of the stack is free to be used again.

How does the command prompt know when to wait for exit?

79 votes

I was attempting to do a Windows command prompt re-code in C#. I was wondering how the command prompt knows when to wait for the process started to exit, and when not to wait for the called process to exit.

For example, if you type in the command prompt "notepad", Notepad will launch, but you can still execute other commands. However, if you open a utility such as more.com, ping.exe, or another utility, it will wait for the executing program to finish before letting you execute another command.

How does the command prompt know when to wait for exit, and how can this behavior be emulated in C#?

If the application is a Win32 GUI application, it will just run and command prompt won't wait for it to exit.

If the application is a console application, it will run in the command prompt and you'll need to wait for it to finish to get the command prompt back.

EDIT:

OK. It seems you need technical explanation. If you want to emulate the same feature in your application, you can check IMAGE_OPTIONAL_HEADER of EXE files here.

Inside IMAGE_OPTIONAL_HEADER, there is:

 WORD                 Subsystem;

If SubSystem == 0x02 it means it's a GUI application.

If SubSystem == 0x03 it means it's a command prompt app.

EDIT 2:

If you want to see it in action:

  1. Download http://www.ntcore.com/exsuite.php

  2. Copy calc.exe or notepad.exe to your desktop

  3. Open copied calc.exe in CFF Explorer

  4. Navigate to Nt Headers -> Optional Headers

  5. Change SubSystem from 0x002 to 0x003

  6. Save it

Now run the new modified calc and you'll see the command prompt wait for it to be terminated.

Why do C and C++ compilers allow array lengths in function signatures when they're never enforced?

72 votes

This is what I found during my learning period:

#include<iostream>
using namespace std;
int dis(char a[1])
{
    int length=strlen(a);
    char c=a[2];
    return length;
}
int main()
{
    char b[4]="abc";
    int c=dis(b);
    cout<<c;
    return 0;
}  

So in the variable int dis(char a[1]) , the [1] seems to do nothing and doesn't work at
all, because I can use a[2]. Just like int a[] or char *a. I know the array name is a pointer and how to convey an array, so my puzzle is not about this part.

What I want to know is why compilers allow this behavior (int a[1]). Or does it have other meanings that I don't know about?

It is a quirk of the syntax for passing arrays to functions.

Actually it is not possible to pass an array in C. If you write syntax that looks like it should pass the array, what actually happens is that a pointer to the first element of the array is passed instead.

Since the pointer does not include any length information, the contents of your [] in the function formal parameter list are actually ignored.

The decision to allow this syntax was made in the 1970s and has caused much confusion ever since...

Why are we not to throw these exceptions?

68 votes

I came across this MSDN page that states:

Do not throw System.Exception, System.SystemException, System.NullReferenceException, or System.IndexOutOfRangeException intentionally from your own source code.

Unfortunately, it does not bother to explain why. I can guess at the reasons, but I hope that someone more authoritative on the subject might offer their insight.

The first two make some obvious sense, but the latter two seem like ones you would want to employ (and in fact, I have).

Further, are these the only exceptions one should avoid? If there are others, what are they and why should they, too, be avoided?

Exception is the base type for all exceptions, and as such terribly unspecific. You shouldn’t ever throw this exception because it simply does not contain any useful information. Calling code catching for exceptions couldn’t disambiguate the intentionally thrown exception (from your logic) from other system exceptions that are entirely undesired and point out real faults.

The same reason also applies to SystemException. If you look at the list of derived types, you can see a huge number of other exceptions with very different semantics.

NullReferenceException and IndexOutOfRangeException are of a different kind. Now these are very specific exceptions, so throwing them could be fine. However, you still won’t want to throw these, as they usually mean that there are some actual mistakes in your logic. For example the null reference exception means that you are trying to access a member of an object which is null. If that’s a possibility in your code, then you should always explicitly check for null and throw a more useful exception instead (for example ArgumentNullException). Similarly, IndexOutOfRangeExceptions occur when you access an invalid index (on arrays—not lists). You should always make sure that you don’t do that in the first place and check the boundaries of e.g. an array first.

There are a few other exceptions like those two, for example InvalidCastException or DivideByZeroException, which are thrown for specific faults in your code and usually mean that you are doing something wrong or you are not checking for some invalid values first. By throwing them knowingly from your code, you are just making it harder for the calling code to determine whether they were thrown due some fault in the code, or just because you decided to reuse them for something in your implementation.

Of course, there are some exceptions (hah) to these rules. If you are building something that may cause an exception which exactly matches an existing one, then feel free to use that, especially if you are trying to match some built-in behavior. Just make sure you choose a very specific exception type then.

In general though, unless you find a (specific) exception that fills your need, you should always consider creating your own exception types for specific expected exceptions. Especially when you are writing library code, this can be very useful to separate the exception sources.

How does this magic Javascript work?

60 votes

This is a small javascript that alert "Hello world":

゚ω゚ノ=/`m´)ノ~┻━┻//*´∇`*/['_'];o=(゚ー゚)=_=3;c=(゚Θ゚)=(゚ー゚)-(゚ー゚);(゚Д゚)=(゚Θ゚)=(o^_^o)/(o^_^o);(゚Д゚)={゚Θ゚:'_',゚ω゚ノ:((゚ω゚ノ==3)+'_')[゚Θ゚],゚ー゚ノ:(゚ω゚ノ+'_')[o^_^o-(゚Θ゚)],゚Д゚ノ:((゚ー゚==3)+'_')[゚ー゚]};(゚Д゚)[゚Θ゚]=((゚ω゚ノ==3)+'_')[c^_^o];(゚Д゚)['c']=((゚Д゚)+'_')[(゚ー゚)+(゚ー゚)-(゚Θ゚)];(゚Д゚)['o']=((゚Д゚)+'_')[゚Θ゚];(゚o゚)=(゚Д゚)['c']+(゚Д゚)['o']+(゚ω゚ノ+'_')[゚Θ゚]+((゚ω゚ノ==3)+'_')[゚ー゚]+((゚Д゚)+'_')[(゚ー゚)+(゚ー゚)]+((゚ー゚==3)+'_')[゚Θ゚]+((゚ー゚==3)+'_')[(゚ー゚)-(゚Θ゚)]+(゚Д゚)['c']+((゚Д゚)+'_')[(゚ー゚)+(゚ー゚)]+(゚Д゚)['o']+((゚ー゚==3)+'_')[゚Θ゚];(゚Д゚)['_']=(o^_^o)[゚o゚][゚o゚];(゚ε゚)=((゚ー゚==3)+'_')[゚Θ゚]+(゚Д゚).゚Д゚ノ+((゚Д゚)+'_')[(゚ー゚)+(゚ー゚)]+((゚ー゚==3)+'_')[o^_^o-゚Θ゚]+((゚ー゚==3)+'_')[゚Θ゚]+(゚ω゚ノ+'_')[゚Θ゚];(゚ー゚)+=(゚Θ゚);(゚Д゚)[゚ε゚]='\\';(゚Д゚).゚Θ゚ノ=(゚Д゚+゚ー゚)[o^_^o-(゚Θ゚)];(o゚ー゚o)=(゚ω゚ノ+'_')[c^_^o];(゚Д゚)[゚o゚]='\"';(゚Д゚)['_']((゚Д゚)['_'](゚ε゚+(゚Д゚)[゚o゚]+(゚Д゚)[゚ε゚]+(゚Θ゚)+(゚ー゚)+(゚Θ゚)+(゚Д゚)[゚ε゚]+(゚Θ゚)+((゚ー゚)+(゚Θ゚))+(゚ー゚)+(゚Д゚)[゚ε゚]+(゚Θ゚)+(゚ー゚)+((゚ー゚)+(゚Θ゚))+(゚Д゚)[゚ε゚]+(゚Θ゚)+((o^_^o)+(o^_^o))+((o^_^o)-(゚Θ゚))+(゚Д゚)[゚ε゚]+(゚Θ゚)+((o^_^o)+(o^_^o))+(゚ー゚)+(゚Д゚)[゚ε゚]+((゚ー゚)+(゚Θ゚))+(c^_^o)+(゚Д゚)[゚ε゚]+(゚ー゚)+((o^_^o)-(゚Θ゚))+(゚Д゚)[゚ε゚]+(゚Θ゚)+(゚Θ゚)+(c^_^o)+(゚Д゚)[゚ε゚]+(゚Θ゚)+(゚ー゚)+((゚ー゚)+(゚Θ゚))+(゚Д゚)[゚ε゚]+(゚Θ゚)+((゚ー゚)+(゚Θ゚))+(゚ー゚)+(゚Д゚)[゚ε゚]+(゚Θ゚)+((゚ー゚)+(゚Θ゚))+(゚ー゚)+(゚Д゚)[゚ε゚]+(゚Θ゚)+((゚ー゚)+(゚Θ゚))+((゚ー゚)+(o^_^o))+(゚Д゚)[゚ε゚]+(゚ー゚)+(c^_^o)+(゚Д゚)[゚ε゚]+(゚Θ゚)+((o^_^o)-(゚Θ゚))+((゚ー゚)+(o^_^o))+(゚Д゚)[゚ε゚]+(゚Θ゚)+((゚ー゚)+(゚Θ゚))+((゚ー゚)+(o^_^o))+(゚Д゚)[゚ε゚]+(゚Θ゚)+((o^_^o)+(o^_^o))+((o^_^o)-(゚Θ゚))+(゚Д゚)[゚ε゚]+(゚Θ゚)+((゚ー゚)+(゚Θ゚))+(゚ー゚)+(゚Д゚)[゚ε゚]+(゚Θ゚)+(゚ー゚)+(゚ー゚)+(゚Д゚)[゚ε゚]+(゚ー゚)+((o^_^o)-(゚Θ゚))+(゚Д゚)[゚ε゚]+((゚ー゚)+(゚Θ゚))+(゚Θ゚)+(゚Д゚)[゚o゚])(゚Θ゚))('_');

A good looking version:

゚ω゚ノ = /`m´)ノ~┻━┻//*´∇`*/['_'];
o = (゚ー゚) = _ = 3;
c = (゚Θ゚) = (゚ー゚) - (゚ー゚);
(゚Д゚) = (゚Θ゚) = (o^_^o)/(o^_^o);
(゚Д゚) = {
  ゚Θ゚:  '_',
  ゚ω゚ノ: ((゚ω゚ノ==3)+'_')[゚Θ゚],
  ゚ー゚ノ: (゚ω゚ノ+'_')[o^_^o-(゚Θ゚)],
  ゚Д゚ノ: ((゚ー゚==3)+'_')[゚ー゚]
};
(゚Д゚)[゚Θ゚] = ((゚ω゚ノ==3)+'_')[c^_^o];
(゚Д゚)['c'] = ((゚Д゚)+'_')[(゚ー゚)+(゚ー゚)-(゚Θ゚)];
(゚Д゚)['o'] = ((゚Д゚)+'_')[゚Θ゚];
(゚o゚)=(゚Д゚)['c'] + (゚Д゚)['o'] + (゚ω゚ノ + '_')[゚Θ゚] + ((゚ω゚ノ==3) + '_')[゚ー゚] + ((゚Д゚) + '_')[(゚ー゚) + (゚ー゚)] + ((゚ー゚==3) + '_')[゚Θ゚] + ((゚ー゚==3) + '_')[(゚ー゚) - (゚Θ゚)] + (゚Д゚)['c'] + ((゚Д゚) + '_')[(゚ー゚) + (゚ー゚)] + (゚Д゚)['o'] + ((゚ー゚==3) + '_')[゚Θ゚];
(゚Д゚)['_'] = (o^_^o)[゚o゚][゚o゚];
(゚ε゚) = ((゚ー゚==3) + '_')[゚Θ゚] + (゚Д゚).゚Д゚ノ + ((゚Д゚) + '_')[(゚ー゚) + (゚ー゚)] + ((゚ー゚==3) + '_')[o^_^o-゚Θ゚] + ((゚ー゚==3) + '_')[゚Θ゚] + (゚ω゚ノ+'_')[゚Θ゚];
(゚ー゚) += (゚Θ゚);
(゚Д゚)[゚ε゚] = '\\';
(゚Д゚).゚Θ゚ノ = (゚Д゚+゚ー゚)[o^_^o-(゚Θ゚)];
(o゚ー゚o) = (゚ω゚ノ+'_')[c^_^o];
(゚Д゚)[゚o゚] = '\"';
(゚Д゚)['_']((゚Д゚)['_'](゚ε゚+(゚Д゚)[゚o゚]+(゚Д゚)[゚ε゚]+(゚Θ゚)+(゚ー゚)+(゚Θ゚)+(゚Д゚)[゚ε゚]+(゚Θ゚)+((゚ー゚)+(゚Θ゚))+(゚ー゚)+(゚Д゚)[゚ε゚]+(゚Θ゚)+(゚ー゚)+((゚ー゚)+(゚Θ゚))+(゚Д゚)[゚ε゚]+(゚Θ゚)+((o^_^o)+(o^_^o))+((o^_^o)-(゚Θ゚))+(゚Д゚)[゚ε゚]+(゚Θ゚)+((o^_^o)+(o^_^o))+(゚ー゚)+(゚Д゚)[゚ε゚]+((゚ー゚)+(゚Θ゚))+(c^_^o)+(゚Д゚)[゚ε゚]+(゚ー゚)+((o^_^o)-(゚Θ゚))+(゚Д゚)[゚ε゚]+(゚Θ゚)+(゚Θ゚)+(c^_^o)+(゚Д゚)[゚ε゚]+(゚Θ゚)+(゚ー゚)+((゚ー゚)+(゚Θ゚))+(゚Д゚)[゚ε゚]+(゚Θ゚)+((゚ー゚)+(゚Θ゚))+(゚ー゚)+(゚Д゚)[゚ε゚]+(゚Θ゚)+((゚ー゚)+(゚Θ゚))+(゚ー゚)+(゚Д゚)[゚ε゚]+(゚Θ゚)+((゚ー゚)+(゚Θ゚))+((゚ー゚)+(o^_^o))+(゚Д゚)[゚ε゚]+(゚ー゚)+(c^_^o)+(゚Д゚)[゚ε゚]+(゚Θ゚)+((o^_^o)-(゚Θ゚))+((゚ー゚)+(o^_^o))+(゚Д゚)[゚ε゚]+(゚Θ゚)+((゚ー゚)+(゚Θ゚))+((゚ー゚)+(o^_^o))+(゚Д゚)[゚ε゚]+(゚Θ゚)+((o^_^o)+(o^_^o))+((o^_^o)-(゚Θ゚))+(゚Д゚)[゚ε゚]+(゚Θ゚)+((゚ー゚)+(゚Θ゚))+(゚ー゚)+(゚Д゚)[゚ε゚]+(゚Θ゚)+(゚ー゚)+(゚ー゚)+(゚Д゚)[゚ε゚]+(゚ー゚)+((o^_^o)-(゚Θ゚))+(゚Д゚)[゚ε゚]+((゚ー゚)+(゚Θ゚))+(゚Θ゚)+(゚Д゚)[゚o゚])(゚Θ゚))('_');

JSFiddle

Taken from here: http://codegolf.stackexchange.com/a/24041/17049

Anyone have any idea how it works? I don't even see the alert in that code.

Before looking closer at the code, you have to know that since JavaScript 1.5 identifiers are allowed to contain not just ASCII characters but also Unicode characters.

In this case many of these funny sequences are just identifiers. After exchanging these identifiers by simpler identifiers and removing unnecessary comments and parenthesis, the code looks as follows:

a = /`m´)ノ~┻━┻/['_'];
o = b = _ = 3;
c = d = b-b;
e = d = o^_^o/o^_^o;
e = {
  d: '_',
  a: ((a==3)+'_')[d],
  h: (a+'_')[o^_^o-d],
  i: ((b==3)+'_')[b]
};
e[d]   = ((a==3)+'_')[c^_^o];
e['c'] = (e+'_')[b+b-d];
e['o'] = (e+'_')[d];
f      = e['c']+e['o']+(a+'_')[d]+((a==3)+'_')[b]+(e+'_')[b+b]+((b==3)+'_')[d]+((b==3)+'_')[b-d]+e['c']+(e+'_')[b+b]+e['o']+((b==3)+'_')[d];
e['_'] = (o^_^o)[f][f];
g      = ((b==3)+'_')[d]+e.i+(e+'_')[b+b]+((b==3)+'_')[o^_^o-d]+((b==3)+'_')[d]+(a+'_')[d];
b      += d;
e[g]   = '\\';
e.j    = (e+b)[o^_^o-d];
obo    = (a+'_')[c^_^o];
e[f]   = '\"';
e['_'](e['_'](g+e[f]+e[g]+d+b+d+e[g]+d+(b+d)+b+e[g]+d+b+(b+d)+e[g]+d+((o^_^o)+(o^_^o))+((o^_^o)-d)+e[g]+d+((o^_^o)+(o^_^o))+b+e[g]+(b+d)+(c^_^o)+e[g]+b+((o^_^o)-d)+e[g]+d+d+(c^_^o)+e[g]+d+b+(b+d)+e[g]+d+(b+d)+b+e[g]+d+(b+d)+b+e[g]+d+(b+d)+(b+(o^_^o))+e[g]+b+(c^_^o)+e[g]+d+((o^_^o)-d)+(b+(o^_^o))+e[g]+d+(b+d)+(b+(o^_^o))+e[g]+d+((o^_^o)+(o^_^o))+((o^_^o)-d)+e[g]+d+(b+d)+b+e[g]+d+b+b+e[g]+b+((o^_^o)-d)+e[g]+(b+d)+d+e[f])(d))('_');

Now we’re able to evaluate each statement at a time:

  • a = /`m´)ノ~┻━┻/['_'] evaluates to a = undefined
  • o = b = _ = 3 assigns o, b, and _ the integer 3
  • c = d = b-b assigns c and d the integer 0
  • e = d = o^_^o/o^_^o assigns e and d the integer 1 (o^_^o evaluates to 3 XOR 3 XOR 3, which yields 3)
  • e = { d: '_', a: ((a==3)+'_')[d], h: (a+'_')[o^_^o-d], i: ((b==3)+'_')[b] } assigns e the object { d: '_', a: 'a', h: 'd', i: 'e' }
  • e[d] = ((a==3)+'_')[c^_^o] assigns e[1] the string 'f'
  • e['c'] = (e+'_')[b+b-d] assigns e['c'] the string 'c'
  • e['o'] = (e+'_')[d] assigns e['o'] the string 'o'

This was all just the setup and the following variables are set:

a = undefined
b = 3
c = 0
d = 1
e = {
    1: "f",
    a: "a",
    c: "c",
    d: "_",
    h: "d",
    i: "e",
    o: "o"
}

The next statement is the first that constructs something:

f = e['c'] +             // => "c"
    e['o'] +             // => "o"
    (a+'_')[d] +         // => "undefined_"[1] = "n"
    ((a==3)+'_')[b] +    // => "false_"[3]     = "s"
    (e+'_')[b+b] +       // => "object_"[6]    = "t"
    ((b==3)+'_')[d] +    // => "true_"[1]      = "r"
    ((b==3)+'_')[b-d] +  // => "true_"[2]      = "s"
    e['c'] +             // => "c"
    (e+'_')[b+b] +       // => "object_"[6]    = "t"
    e['o'] +             // => "o"
    ((b==3)+'_')[d];     // => "true"[1]       = "r"

So f = "constructor". In the next statement this "constructor" is used to retrieve a function:

e['_'] = (o^_^o)[f][f]

This is equivalent to (3).constructor.constructor, which yields the function Function, so:

e['_'] = Function

This Function function is special as one can construct functions dynamically by passing it the function body code via parameter:

f = Function("alert(1)")
// equivalent to
f = function() { alert(1) }

I’ll skip the next few statements and just write the resulting variables and values:

a = undefined
b = 4
c = 0
d = 1
e = {
    1: "f",
    _: Function,
    a: "a",
    c: "c",
    constructor: "\"",
    d: "_",
    h: "d",
    i: "e",
    j: "b",
    o: "o",
    return: "\\"
}
f = "constructor"
obo = "u"

The last statement does the final work:

e['_'](e['_'](g+e[f]+e[g]+d+b+d+e[g]+d+(b+d)+b+e[g]+d+b+(b+d)+e[g]+d+((o^_^o)+(o^_^o))+((o^_^o)-d)+e[g]+d+((o^_^o)+(o^_^o))+b+e[g]+(b+d)+(c^_^o)+e[g]+b+((o^_^o)-d)+e[g]+d+d+(c^_^o)+e[g]+d+b+(b+d)+e[g]+d+(b+d)+b+e[g]+d+(b+d)+b+e[g]+d+(b+d)+(b+(o^_^o))+e[g]+b+(c^_^o)+e[g]+d+((o^_^o)-d)+(b+(o^_^o))+e[g]+d+(b+d)+(b+(o^_^o))+e[g]+d+((o^_^o)+(o^_^o))+((o^_^o)-d)+e[g]+d+(b+d)+b+e[g]+d+b+b+e[g]+b+((o^_^o)-d)+e[g]+(b+d)+d+e[f])(d))('_');

This is equivalent to:

Function(Function( … )(1))('_')

The long expression builds the following string:

return"\141\154\145\162\164\50\42\110\145\154\154\157\40\127\157\162\154\144\42\51"

The escaped string evaluates:

alert("Hello World")

This return code is passed to Function, which creates an anonymous function like:

function anonymous() {
    return"\141\154\145\162\164\50\42\110\145\154\154\157\40\127\157\162\154\144\42\51";
}

Which, we know, is equivalent to:

function anonymous() {
    return"alert(\"Hello World\")";
}

This function is then executed with 1 as parameter, which returns the resulting string:

alert("Hello World")

This is then passed to Function again, which creates a new anonymous function:

function anonymous() {
    alert("Hello World");
}

Finally, this function is also invoked with '_' as parameter.

Java 8 stream's .min() and .max(): why does this compile?

59 votes

Note: question originally posted here, but it has since been deleted...

See this code (I know, it is absurd -- I just extracted it from the linked question):

ArrayList <Integer> list = new ArrayList<>();
for (int i = 1; i <= 20; i++)
    list.add(i);

System.out.println(list.stream().max(Integer::max).get());
System.out.println(list.stream().min(Integer::min).get());

According to the javadoc of .min() and .max(), the argument of both should be a Comparator. Yet here the method references are to static methods of the Integer class.

So, why does this compile at all?

Let me explain what is happening here, because it isn't obvious!

First, Stream.max() accepts an instance of Comparator so that items in the stream can be compared against each other to find the minimum or maximum, in some optimal order that you don't need to worry too much about.

So the question is, of course, why is Integer::max accepted? After all it's not a comparator!

The answer is in the way that the new lambda functionality works in Java 8. It relies on a concept which is informally known as "single abstract method" interfaces, or "SAM" interfaces. The idea is that any interface with one abstract method can be automatically implemented by any lambda - or method reference - whose method signature is a match for the one method on the interface. So examining the Comparator interface (simple version):

public Comparator<T> {
    int compare(T o1, T o2);
}

If a method is looking for a Comparator<Integer>, then it's essentially looking for this signature:

int xxx(Integer o1, Integer o2);

I use "xxx" because the method name is not used for matching purposes.

Now Math.min/max() have the following signature:

int min(int i1, int i2);

This is close enough that autoboxing will allow this to appear as a Comparator<Integer> in a method context.

And it means you can use Integer.compare(), since its signature also matches:

System.out.println(list.stream().max(Integer::compare).get());
System.out.println(list.stream().min(Integer::compare).get());

Extending a struct in C

58 votes

I recently came across a colleague's code that looked like this:

typedef struct A {
  int x;
}A;

typedef struct B {
  A a;
  int d;
}B;

void fn(){
  B *b;
  ((A*)b)->x = 10;
}

His explanation was that since struct A was the first member of struct B, so b->x would be the same as b->a.x and provides better readability.
This makes sense, but is this considered good practice? And will this work across platforms? Currently this runs fine on GCC.

Yes, it will work cross-platform, but that doesn't necessarily make it a good idea.

As per the ISO C standard (all citations below are from C11), 6.7.2.1 Structure and union specifiers /15, there is not allowed to be padding before the first element of a structure

In addition, 6.2.7 Compatible type and composite type states that:

Two types have compatible type if their types are the same

and it is undisputed that the A and A-within-B types are identical.

This means that the memory accesses to the A fields will be the same in both A and B types, as would the more sensible b->a.x which is probably what you should be using if you have any concerns about maintainability in future.

And, though you would normally have to worry about strict type aliasing, I don't believe that applies here. It is illegal to alias pointers but the standard has specific exceptions.

6.5 Expressions /7 states some of those exceptions, with the footnote:

The intent of this list is to specify those circumstances in which an object may or may not be aliased.

The exceptions listed are:

  • a type compatible with the effective type of the object;
  • some other exceptions which need not concern us here; and
  • an aggregate or union type that includes one of the aforementioned types among its members (including, recursively, a member of a subaggregate or contained union).

That, combined with the struct padding rules mentioned above, including the phrase:

A pointer to a structure object, suitably converted, points to its initial member

seems to indicate this example is specifically allowed for. The core point we have to remember here is that the type of the expression ((A*)b) is A*, not B*. That makes the variables compatible for the purposes of unrestricted aliasing.

That's my reading of the relevant portions of the standard, I've been wrong before (a), but I doubt it in this case.

So, if you have a genuine need for this, it will work okay but I'd be documenting any constraints in the code very close to the structures so as to not get bitten in future.


(a) As my wife will tell you, frequently and without much prompting :-)

What's an appropriate search/retrieval method for a VERY long list of strings?

58 votes

This is not a terribly uncommon question, but I still couldn't seem to find an answer that really explained the choice.

I have a very large list of strings (ASCII representations of SHA-256 hashes, to be exact), and I need to query for the presence of a string within that list.

There will be what is likely in excess of 100 million entries in this list, and I will need to repeatably query for the presence of an entry many times.

Given the size, I doubt I can stuff it all into a HashSet<string>. What would be an appropriate retrieval system to maximize performance?

I CAN pre-sort the list, I CAN put it into a SQL table, I CAN put it into a text file, but I'm not sure what really makes the most sense given my application.

Is there a clear winner in terms of performance among these, or other methods of retrieval?

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Security.Cryptography;

namespace HashsetTest
{
    abstract class HashLookupBase
    {
        protected const int BucketCount = 16;

        private readonly HashAlgorithm _hasher;

        protected HashLookupBase()
        {
            _hasher = SHA256.Create();
        }

        public abstract void AddHash(byte[] data);
        public abstract bool Contains(byte[] data);

        private byte[] ComputeHash(byte[] data)
        {
            return _hasher.ComputeHash(data);
        }

        protected Data256Bit GetHashObject(byte[] data)
        {
            var hash = ComputeHash(data);
            return Data256Bit.FromBytes(hash);
        }

        public virtual void CompleteAdding() { }
    }

    class HashsetHashLookup : HashLookupBase
    {
        private readonly HashSet<Data256Bit>[] _hashSets;

        public HashsetHashLookup()
        {
            _hashSets = new HashSet<Data256Bit>[BucketCount];

            for(int i = 0; i < _hashSets.Length; i++)
                _hashSets[i] = new HashSet<Data256Bit>();
        }

        public override void AddHash(byte[] data)
        {
            var item = GetHashObject(data);
            var offset = item.GetHashCode() & 0xF;
            _hashSets[offset].Add(item);
        }

        public override bool Contains(byte[] data)
        {
            var target = GetHashObject(data);
            var offset = target.GetHashCode() & 0xF;
            return _hashSets[offset].Contains(target);
        }
    }

    class ArrayHashLookup : HashLookupBase
    {
        private Data256Bit[][] _objects;
        private int[] _offsets;
        private int _bucketCounter;

        public ArrayHashLookup(int size)
        {
            size /= BucketCount;
            _objects = new Data256Bit[BucketCount][];
            _offsets = new int[BucketCount];

            for(var i = 0; i < BucketCount; i++) _objects[i] = new Data256Bit[size + 1];

            _bucketCounter = 0;
        }

        public override void CompleteAdding()
        {
            for(int i = 0; i < BucketCount; i++) Array.Sort(_objects[i]);
        }

        public override void AddHash(byte[] data)
        {
            var hashObject = GetHashObject(data);
            _objects[_bucketCounter][_offsets[_bucketCounter]++] = hashObject;
            _bucketCounter++;
            _bucketCounter %= BucketCount;
        }

        public override bool Contains(byte[] data)
        {
            var hashObject = GetHashObject(data);
            return _objects.Any(o => Array.BinarySearch(o, hashObject) >= 0);
        }
    }

    struct Data256Bit : IEquatable<Data256Bit>, IComparable<Data256Bit>
    {
        public bool Equals(Data256Bit other)
        {
            return _u1 == other._u1 && _u2 == other._u2 && _u3 == other._u3 && _u4 == other._u4;
        }

        public int CompareTo(Data256Bit other)
        {
            var rslt = _u1.CompareTo(other._u1);    if (rslt != 0) return rslt;
            rslt = _u2.CompareTo(other._u2);        if (rslt != 0) return rslt;
            rslt = _u3.CompareTo(other._u3);        if (rslt != 0) return rslt;

            return _u4.CompareTo(other._u4);
        }

        public override bool Equals(object obj)
        {
            if (ReferenceEquals(null, obj))
                return false;
            return obj is Data256Bit && Equals((Data256Bit) obj);
        }

        public override int GetHashCode()
        {
            unchecked
            {
                var hashCode = _u1.GetHashCode();
                hashCode = (hashCode * 397) ^ _u2.GetHashCode();
                hashCode = (hashCode * 397) ^ _u3.GetHashCode();
                hashCode = (hashCode * 397) ^ _u4.GetHashCode();
                return hashCode;
            }
        }

        public static bool operator ==(Data256Bit left, Data256Bit right)
        {
            return left.Equals(right);
        }

        public static bool operator !=(Data256Bit left, Data256Bit right)
        {
            return !left.Equals(right);
        }

        private readonly long _u1;
        private readonly long _u2;
        private readonly long _u3;
        private readonly long _u4;

        private Data256Bit(long u1, long u2, long u3, long u4)
        {
            _u1 = u1;
            _u2 = u2;
            _u3 = u3;
            _u4 = u4;
        }

        public static Data256Bit FromBytes(byte[] data)
        {
            return new Data256Bit(
                BitConverter.ToInt64(data, 0),
                BitConverter.ToInt64(data, 8),
                BitConverter.ToInt64(data, 16),
                BitConverter.ToInt64(data, 24)
            );
        }
    }

    class Program
    {
        private const int TestSize = 150000000;

        static void Main(string[] args)
        {
            GC.Collect(3);
            GC.WaitForPendingFinalizers();

            {
                var arrayHashLookup = new ArrayHashLookup(TestSize);
                PerformBenchmark(arrayHashLookup, TestSize);
            }

            GC.Collect(3);
            GC.WaitForPendingFinalizers();

            {
                var hashsetHashLookup = new HashsetHashLookup();
                PerformBenchmark(hashsetHashLookup, TestSize);
            }

            Console.ReadLine();
        }

        private static void PerformBenchmark(HashLookupBase hashClass, int size)
        {
            var sw = Stopwatch.StartNew();

            for (int i = 0; i < size; i++)
                hashClass.AddHash(BitConverter.GetBytes(i * 2));

            Console.WriteLine("Hashing and addition took " + sw.ElapsedMilliseconds + "ms");

            sw.Restart();
            hashClass.CompleteAdding();
            Console.WriteLine("Hash cleanup (sorting, usually) took " + sw.ElapsedMilliseconds + "ms");

            sw.Restart();
            var found = 0;

            for (int i = 0; i < size * 2; i += 10)
            {
                found += hashClass.Contains(BitConverter.GetBytes(i)) ? 1 : 0;
            }

            Console.WriteLine("Found " + found + " elements (expected " + (size / 5) + ") in " + sw.ElapsedMilliseconds + "ms");
        }
    }
}

Results are pretty promising. They run single-threaded. The hashset version can hit a little over 1 million lookups per second at 7.9GB RAM usage. The array-based version uses less RAM (4.6GB). Startup times between the two are nearly identical (388 vs 391 seconds). The hashset trades RAM for lookup performance. Both had to be bucketized because of memory allocation constraints.

Array performance:

Hashing and addition took 307408ms

Hash cleanup (sorting, usually) took 81892ms

Found 30000000 elements (expected 30000000) in 562585ms [53k searches per second]

======================================

Hashset performance:

Hashing and addition took 391105ms

Hash cleanup (sorting, usually) took 0ms

Found 30000000 elements (expected 30000000) in 74864ms [400k searches per second]

Empty string as a special case?

56 votes

I read Jon Skeet's quiz and I wondered why the second sample of mine won't work while the first one does.

Why does this yield true :

object x = new string("".ToArray());
object y = new string("".ToArray());
Console.WriteLine(x == y); //true

But this one does not:

var k="k";
//string.intern(k); // doesn't help
object x = new string(k.ToArray());
object y = new string(k.ToArray());
Console.WriteLine(x == y); //false

I'm using fw 4.5 with vs2010.

Luckily I also have vs2005 installed , same results :

enter image description here

Here is a blog post by Eric Lippert which answers your question: String interning and String.Empty.

He's describing similar situation:

object obj = "Int32";
string str1 = "Int32";
string str2 = typeof(int).Name;
Console.WriteLine(obj == str1); // true
Console.WriteLine(str1 == str2); // true
Console.WriteLine(obj == str2); // false !?

So the idea is, that interning does not mean you'll have only one instance of particular string, even when it's interned. Only compile time literals are interned by default. It means that following code prints true:

var k1 = "k";
object k2 = "k";
Console.WriteLine(k1 == k2);

But, if you try to create string with "k" content programmatically at runtime, e.g. using string(char[]) constructor, calling ToString() on an object, using StringBuilder, etc, you won't get interned string by default. This one prints false;

var k1 = "k";
object k2 = new string("k".ToCharArray());
Console.WriteLine(k1 == k2);

Why? Because interning strings at runtime is expensive.

There Ain't No Such Thing As A Free Lunch.

(...)

In short, it is in the general case not worth it to intern all strings.

And about different behavior with empty string:

Some versions of the .NET runtime automatically intern the empty string at runtime, some do not!

How do I check if a zero is positive or negative?

53 votes

Is it possible to check if a float is a positive zero (0.0) or a negative zero (-0.0)?

I've converted the float to a String and checked if the first char is a '-', but are there any other ways?

Yes, divide by it. 1 / +0.0f is +Infinity, but 1 / -0.0f is -Infinity. It's easy to find out which one it is with a simple comparison, so you get:

if (1 / x > 0)
    // +0 here
else
    // -0 here

(this assumes that x can only be one of the two zeroes)

Why does .NET behave so poorly when StackOverflowException is thrown?

47 votes

I'm aware that StackOverflowExceptions in .NET can't be caught, take down their process, and have no stack trace. This is officially documented on MSDN. However, I'm wondering what the technical (or other) reasons are behind the behavior. All MSDN says is:

In prior versions of the .NET Framework, your application could catch a StackOverflowException object (for example, to recover from unbounded recursion). However, that practice is currently discouraged because significant additional code is required to reliably catch a stack overflow exception and continue program execution.

What is this "significant additional code"? Are there other documented reasons for this behavior? Even if we can't catch SOE, why can't we at least get a stack trace? Several co-workers and I just sunk several hours into debugging a production StackOverflowException that would have taken minutes with a stack trace, so I'm wondering if there is a good reason for my suffering.

The stack of a thread is created by Windows. It uses so-called guard pages to be able to detect a stack overflow. A feature that's generally available to user mode code as described in this MSDN Library article. The basic idea is that the last two pages of the stack (2 x 4096 = 8192 bytes) are reserved and any processor access to them triggers a page fault that's turned into an SEH exception, STATUS_GUARD_PAGE_VIOLATION.

This is intercepted by the kernel in the case of those pages belonging to a thread stack. It changes the protection attributes for those 2 pages, thus giving the thread some emergency stack space to deal with the mishap, then re-raises a STATUS_STACK_OVERFLOW exception.

This exception is in turn intercepted by the CLR. At that point there's about 7 kilobytes of stack space left. This is, for one, not enough to run the Just-in-time compiler (JITter) to compile the code that could deal with the exception in your program, the JITter needs much more space than that. The CLR therefore cannot do anything else but rudely abort the thread. And by .NET 2.0 policy that also terminates the process.

This for one explains why this is not a problem in Java, it can interpret bytecode that isn't JITted yet so there's a guarantee that executable user code can run. Or in a non-managed program written in languages like C, C++ or Delphi, code is generated at build time. It is still a very difficult mishap to deal with, the emergency space in the stack is blown so there is no scenario where continuing to run code on the thread is safe to do. The likelihood that a program can continue operating correctly with a thread aborted at a completely random location and rather corrupted state is quite unlikely.

If there was any effort at all in considering raising an event on another thread or in removing the restriction in the winapi (the number of guard pages is not configurable) then that's either a very well-kept secret or just wasn't considered useful. I suspect the latter, don't know it for a fact.

xcode 5.1: libCordova.a architecture problems

43 votes

Yesterday (3/10/14) when iOS 7.1 was released I also upgraded to Xcode 5.1 and found that my PhoneGap/Cordova project would no longer compile to my iPhone 5s. I also upgraded Cordova to the most recent release: v 3.4.0-0.1.3.

I have read many different solutions on SO that relate so changing active architectures and building only active architectures, and none of them work. So here's what I've tried and the errors I get. Initially I got the error:

missing required architecture arm64 in file <long file path omitted> libCordova.a
Undefined symbols for architecture arm64

So I tried the following. I selected the CordovaLib sub-project in my project, and in both the project and target, I went to Build Settings under Architectures and made sure that arm64 was not included in any of the Debug or Release architectures. At this time Build Active Architecture Only is set to "Yes". That resulted in the following error:

file was built for archive which is not the architecture being linked (armv7): 
<long file path omitted> libCordova.a
Undefined symbols for architecture armv7

Setting Build Active Architecture Only to "No", the error again becomes:

missing required architecture arm64 in file <long file path omitted> libCordova.a
Undefined symbols for architecture arm64

I'm not sure what else to try. The project's architecture settings only includes the key "Base SDK" which is set to iOS 7.1. The project's target does not have architectures settings. Anyway I'm fairly certain the problem lies with the embedded CordovaLib sub-project. What can I do to make this thing compile to my device successfully?

Update: same issue on Apache's Jira: https://issues.apache.org/jira/browse/CB-6223

@Shazron posted the fix on the Apache JIRA - he notes that the fix will be released as part of Cordova 3.5:

  1. Select your Project icon
  2. Choose Build Settings.
  3. For "Architectures", select $ARCHS_STANDARD - Standard architectures (armv7, armv7s, arm64)
  4. For "Valid Architectures", add "arm64"
  5. Select your CordovaLib.xcodeproj icon
  6. In the Build Settings for the Project (not Target), delete the conditional architecture settings (hover to see the minus sign)
  7. For "Architectures", select $ARCHS_STANDARD - Standard architectures (armv7, armv7s, arm64)
  8. For "Valid Architectures", add "arm64"
  9. Goto 6, but now do it for "Target"

Here's a link to Shazron's complete writeup of this problem: http://shazronatadobe.wordpress.com/2014/03/12/xcode-5-1-and-cordova-ios/