Comments

6 days ago Matt said

- Is it possible to write C programs that do not depend on the CRT? What are the limitations?

Yes, but you have to choose not to. In Visual Studio you can go properties -> Linker -> Ignore All Default Libraries -> True. If you do this you'll also need to turn off buffer security checks and runtime checks in the compiler options and if writing a DLL in compiler -> Advanced set the entry point to "DllMain" or if writing an exe change it to "main".

Things that have to live underneath the CRT (e.g. the Windows libraries, drivers and the kernel) need to do this if you want to build them with visual studio, but it's expected that most programs will want the CRT as it provides all sorts of nice low-performance overhead abstractions on top of the Windows functions exported by the Windows API.

- What is exactly the relationship between the Windows API and the CRT? It looks like the CRT is built on top of Win32 (e.g. malloc calls HeapAlloc) but I came across a few Win32 functions that actually rely on the CRT to do their work.

Microsoft's CRT is built on top of the Windows API (Win32). I'm not sure any core Win32 functions rely on the CRT, but do tell me if I'm wrong.

- Is the Windows NT CRT dll (system32\msvcrt.dll) different from the one that ships with Visual Studio? Can we link our applications with this version of the CRT (and no longer ship the CRT dll with our code)?

Yes. The Windows CRT is the one used by the Windows API dlls, e.g. kernel32.dll uses msvcrt.dll, but your dll will use the CRT shipped as part of your version of Visual Studio. The msvcrt.dll in system32 tends to change only with Windows Service Pack.

- I would love to hear more about the way SEH is implemented (what really happens at the cpu and memory level when an exception is thrown, the search for exception handlers, stack unwinding and so forth). The operating system and the compiler are definitely involved but is the CRT also a part of that?

In I386 processors (the x86 and x64 family if you want to call them that) use PAE to reference memory after Windows XP SP1. PAE allows pages of granularity 4096 bytes to be marked as "paged in" or "not available" and can put additional restrictions on them like "not executable", "not writable" or "uncacheable". When your CPU tries an invalid access to a page in memory, the CPU faults to the page fault handler in the kernel.

A lot of the time page faults are "false positives" - you're touching some memory that is paged out (i.e. put in the pagefile to free up physical ram for other processes), part of a memory mapped file that hasn't been read yet and so on, and these page faults are serviced transparently by the kernel so that user-mode won't ever see them, but occasionally the page is marked as "not available" because you're trying to do something invalid like read an unmapped page or execute on a DEP-protected (NX) page.

At this point the kernel SEH handler kicks in and tries to see if the previous mode was kernel mode. If it was, the kernel services the exception (or bluescreens). If the previous mode was user-mode, it queues an APC request to ntdll's KiUserExceptionDispatcher which is responsible for the user-mode part of SEH. ntdll checks if there are any vectored exception handlers that need to be run, then checks for SEH on the stack via the SEH exception chain. It calls each method in turn and if none of the registered exception handlers want to service the exception, ntdll tells the kernel to tear down the process and invoke the DrWatson crash dialog.

The CRT is not typically involved in the SEH chain, but there are exceptions - the CRT does put SEH checks around several of its functions (i.e. the CRT uses SEH) and the compiler emits vectored exception handlers for many "SEH" try catch blocks (because vectored exception handlers are more safe from attack), but it's not really a CRT thing, it's more of an OS/ntdll thing.

- I believe that some runtime floating point support is built inside the CRT but the source code is not available. Can you share with us some implementation details?

The CRT does have code for "upgrading" the floating point performed on the CPU's FPU chip on processors that have low precision by essentially emulating the floating point behaviour in software. This is configurable in the properties of the compiler as either "fast" or "precise" floating point mode.

- Ntdll.dll also contains some C runtime library functions (mostly string related though), are there similar to the ones implemented in the CRT?

Yes and no. NTDLL is the ultimate base of the Windows user-mode - it's the first thing to be run in the process (long before your main function and long before the CRT) and it provides lots of functionality to the other Windows dlls such as kernel32, advapi, user32 and gdi32. The functionality that it provides is basically added on an ad-hoc basis almost like a somewhat manually invoked CRT for the Win32 libraries themselves, but it's not the same as the Visual Studio CRT even if they share code or if the CRT passes down to the NTDLL implementations.

- How is the CRT designed to be thread-safe and do we still need to call functions like _beginthreadex instead of CreateThread to avoid memory leaks?

Thank you!

The CRT is mostly threadsafe, but you'll have to check on a per function basis. In particular the core functions like heap/thread/file/security are all thread safe.

The _beginthreadex/CreateThread is an old issue, and what matters more than which to use is that you pair _beginthreadex's with _endthreadex and CreateThreads with ExitThread. _beginthreadex is better for the CRT (it gives you SEH wrappers for the entire thread for example) and mixing and matching will cause a small memory leak in the _beginthreadex/ExitThread direction and a possible crash in the CreateThread/_endthreadex direction, so choose one and stick to it.

@damiandixon: If you're doing complex 3D geometry you probably shouldn't be using Direct2D to do it. Direct3D will always always be faster at doing graphics than OpenGL on Windows because Direct3D is a thin layer to the graphics driver's HAL, and OpenGL on Windows thunks to Direct3D anyway.

Charles wrote:


You will see a C++ Expert to Expert interview on C9 in addition to the more broadly-scoped conversations.

Yay! This was an awesome interview btw, and I'd definitely like to see more of these going deep interviews in the near future.

Cheers

deltalmg911 wrote:

I not sure if that is correct.
Incomputability does not equal non-existence. Example the concept of pi. We now it exists though we can't compute it.

Incomputability doesn't mean non-existence, but it does mean the non-existence of a computational answer (i.e. it may exist but it cannot exist within mathematics, since mathematics has a deterministic axiom base and all theorems of mathematics are provable within a finite (albeit large) amount of time). Your case of PI is slightly flawed. PI is computable, and indeed every digit of PI is computable. If you give me a big enough computer and enough time, then for any digit d of Pi I can give you the value of d. This is because although Pi is definited as an infinite sum, the fact that it converges means that if some error margin is allowed, the sum can be trunchated to a finite one. Thus is the d^th digit is required, we just set the error rate to 10^-(d+1) which is a finite sum and thus computable.

On the otherhand it is impossible to compute all the digits of Pi within a finite amount of time (finding a digit d inside a convergent sum of n non-zero values takes time ~O(d/p) where p is the convergent rate of the series, in general therefore, finding any digit that contains an infinity-term (such as the last digit of pi, the infinity-th digit) will take O(infinity) time and therefore is incomputable via this method in finite time).

deltalmg911 wrote:


Similarly we can know that a particle exists somewhere and has a certain probability of being on some region without knowing for sure if it is there or not:  that is  the  definition of probabilistic not deterministic theories. We can claim that quantum mechanics is right because the resulting probablities match what experiment shows the distribution to be, without necessitating that we can but an exact velocity and position vector on each particle in the universe.

As a mathematician at heart I would decline to comment on whether quantum mechanics is "correct" - correctness is physics is dependent on the maths being correct and the world-view transform being correct. If I took the problem of pushing a 1kg mass object with 1 Newton of force, but failed to take into account friction of the object on a surface, then the inaccuracy of my result is due to an inconsistency of my world-view transform rather than of my maths.

Things such as statistical mechanics and the problem of quantum-observation phenomena is not that the result isn't there, but that it can't be measured due to our limited ability to measure it. The Heisenburg effect (which states that measuring a quantum particle limits its degrees of freedom by 1, or more simply that you can't measure speed, spin and velocity of a quantum particle all at once) is dependent so far as I am aware on the limitation that measuring can only be done by projectile analysis. In future we may improve upon this by using other methods, and the solution may become calculable.

paulcoder wrote:



Thus combining the ideas of computability, physics and group theory is not so outlandish after all! You would probably even get it published in a respectable journal.

Unifying theory of computability, group theory and physics

This has already been done. Let's try and get the gist of it down in just a few paragraphs.

The Church-Turing thesis shows that the set of lambda-calculus solvable algorithms is turing complete and that the set of problems that can be solved by a turing machine is the set of algorithms solvable by lambda calculus.

And we have the fact that lambda-calculus is "Goedel-complete" (it is an omega-consistent recursive class k of formulae and this there exists infinitely many problems p for which (given v, a free-variable in r) neither v Gen p not neg( v Gen p ) belong to Flg(k), the set of correct solutions to problems in k).

In brief this means that there are non-computable problems inside lambda-calculus and thus in turing machines, but also (and importantly) there are non-computable problems in mathematics, and turing-unsolvable problems are a subset of problems which cannot be solved in mathematics.

Couple this with the fact that every law of physics is in fact a transformation from a physical "world view" (observations et. al) to a mathematical rule-system and back-again, typically deviating while in the maths stage to do some mathematical transformations before coming back again (the mathematical transform is referred to as the "rule" or physical "law").

For instance, given a mass of 1kg being pushed by 1 Newton of force, we transform this (using physics) to the system {m=1kg, a=1N} and use the transform {F = ma} and solve using mathematics to {a = F/m, a = 1m/ss} and then resolve via physics back again to the statement "it will accellerate by one metre per second per second for the duration the force is applied."

Consequently the problems which cannot be solved by computers is a either equal or a subset of the problems that cannot be solved in physics, which is in turn equal or a subset of the problems that cannot be solved within mathematics (and it is important to note that this is "unfixable"; i.e. we cannot change maths to compensate for this, since it will either be incomplete (we don't know everything) or inconsistent (we've proved some things which don't happen)).

So there is a unifcation set for you which combines group theory, unsolvability and physics.

On why there is almost certainly no Theory of Everything (and caveats conditions for its existence)

Finally we should note that if a theory of everything T existed then we would be able to ask it any question in physics and it must finitely terminate with the correct answer as to what will happen. But if this theory T is to exist within science it must be rigourous, and thus must be itself a subset of mathematics. Given a statement p inside the axiomatic-world-view of physics we then know (given that T always finitely terminates with the correct result) that for a free-variable v in  T then v Gen p lies inside the set of provable statements in T, the so-called Flg(T). But I know from Goedel's theorem that there exists a statement x inside T for which neither v Gen x nor neg(v Gen x) exists inside Flg(T) and so consequently choosing p = x we have a contradiction.

It therefore follows that either one of the following is true:

• A theory of everything exists, but it cannot be written in mathematics. At which point it stops being science and becomes philosophy or theology.
• A theory of everything exists, but for some problems it simply returns the wrong result.
  
• A theory of everything exists, but for some problems it will never return a result. And equally importantly given Turing's halting problem you won't be able to tell before doing the computation that it will never halt. Consequently the theory ceases to be a theory of "everything" in the sense that we know it.
• A theory of everything exists, but it can't tell you everything about "everything", only somethings about everything (or everything about something), and thus isn't really a theory of everything.
  
• A theory of everything simply does not exist

KevinB wrote:



Yeah, the 30 minutes was an achievement, but I must admit this stretched my April Fool's good humour to the limit, 30 minutes of listening to the WMA and then it is an April Fool's. Funny, which is why I didn't do the first post warning others it was an April Fool's, but just a little too long and too much time wasted for comfort...

It's not time wasted. It's a great discussion on the history of physics (everything up to and including the existance of the set E8 is true - whether E8 unifies anything in physics is spurious at best and everything after that is New Scientist article lies).

And if you didn't cotton-on to the fact that it's an april fool joke by the time Brian says they "finished" theoretical physics then shame on you

This all being said, given that quantum computing actually exists (stop laughing) I wonder if Microsoft does actually have any active interests in that area.

dcharles wrote:

Truely old school, he wrote his algorithm on paper! how many programmers do that today? 

Me for one. Excepting trivial functions, most of what I do requires me to think, and I can't do that without a bit of paper and a pencil.

jason818_253.33 wrote:  Regarding the Sleeping Barber Algorithm and with out breaking the demonstration. Wouldn’t you want to have as many barbers as you have chairs?

CRPietschmann wrote:

This analogy does make the problem sound simple.

You've both misunderstood the crux of the Sleeping Barber problem. The problem is a problem not of speed or efficiency, but one of concurrency. The point is to serve the customers without experiencing process- (customer-) starvation or deadlock and the Sleeping Barber problem is a double-rendevous problem requring a more careful use of locks to achieve the correct result than you might think at first.

Wizarr wrote:



Maybe have a new keyword called "spnew" that replaces or adds to the "new" keyword where it automatically handles where it gets allocated from.  Then the type can be infered by the spnew operation so that is bypasses the gc but add attributes to tell the gc the scope for deletion.  I havent really looked too hard at how best you can describe this feature but I think you can have them coexists.

I think you should have a look at managed C++ - we have two keywords: new works the same as in normal C++ and gcnew tells the garbage collector that it is responsible for cleaning up the object. This allows you to use the sharedpointer semantics for C++ types, and use the garbage collector for the .NET components.

Wizarr wrote:



If we can make dotnet more honest, I think we will have more acceptance to things like Haskell and other functional programming languages, while at the same time, being able to have a hybrid version that can handle the problems of Haskell, such as passing around state and how it can handle it.

I think we're abusing the term "honest" here. If you want contractual honesty inside a program this can already be achieved with Spec#. The reason Haskell isn't widely accepted is because saving state is someone messy, and let's face it, most programs are about interacting with the user, which is much more difficult within a functional language.

Wizarr wrote:



As far as the clarifying to my comment about compiler optimization support.  I was just thinking outloud stating, that if the compiler was smart enough, then we dont need to declarative state that we want this referenced counted, it can infer it automatically if all certian conditions of isolation are met.  Like all other optimizations, we never tell the compiler to change our code but it does so if it thinks it can guarentee the same output but faster.

I suspect we'll have to wait for TR1 to become part of the C++ standard before anything like this happens, but certainly the compilers will (and already do) infer usage patterns from your code and replace or insert mechanisms of achieving the same result but in less memory, code or time.

Wizarr wrote:



Not meaning to downplay how cool these additions sound to c++, but as a c# developer, it seriously begs the question.  Is it possible to enable a more declarative syntax to c# that allows you to create a special mode in the managed .net environment where you can bypass the garbage collection?  If you can prove to the complier that you will have deterministic destruction via these "shared pointers" that will be enforced by the runtime and reference counted I think that will lessen the burden of garbage collecting to those individual resources and speed up your code and be more memory efficient.

Sure it's possible, but this problem is being arrived at from different perspectives. In dotNET pretty much everything lives on the heap. When you do a new object() or a new array[] construction, the item is built onto the heap, and the thing you are storing in your variable is a reference to the object. In C++ when you use a non-indirected structure (such as T value or vector<X> values) you are creating the object on the stack. This means that with C++ it is plausible for the compiler to know which objects need to be disposed as you leave scope, whereas in dotNET leaving scope is independent of the objects on the heap.

This being said, deterministic garbage collection is possible for C#, but it is in general more expensive in terms of CPU cycles. Note that you can bypass the GC entirely by using unsafe code.

Wizarr wrote:



As a side note, I think it's an interesting idea of creating a complier to determine certain code patterns and convert them automatically to be a more efficient managed reference pointing model while providing all the benefits of a managed language.  It could be an option on your compiler optimizer.

It's not entirely clear what you're getting at here. Please elaborate.