An accurate, pauseless & deterministic GC for C++

[Mingnan G.]

The HnxGC Libraray - an accurate, pauseless & deterministic garbage
collector for C++ application, is released at

http://hnxgc.harnixworld.com

(MD5: b96a83d0899317e732abb46a5e1f2dd5)

Features include:

Accurate - HnxGC is a fully accurate tracing garbage collector. We
don't use any tricks to guess/distinguish pointers from other data.
All effective references are identified. There is no leak of garbage
objects uncollected and all associated native resources will be
freed.

Pauseless - HnxGC come with a lock-free and block-free concurrent
collector with no need to scan root-set area. We don't need to take a
snapshot to determine application status, thus the normal execution of
application thread will never be interrupted, suspended, blocked or
forced to spin-waiting by our collector, no matter in a multi-
processors or an uni-processor environment.

Deterministic - HnxGC always executes the destructor of an object when
application program drops the last reference to the object. In
addition, application program can declare dependence rules for each
object to control the destructing ordering of cyclic garbage objects.
The system will figure out an ordering that satisfies all user-
declared rules. Thus, application programmers have more controls on
how unreachable objects are reclaimed, more compliance to RAII
(Resource Acquisition Is Initialization) design pattern, such as
closing file handle or network connection in the destructor routine of
objects.

Efficient - Even HnxGC provide deterministic reclamation feature
similiar to the one in regular reference counting algorithm, we remove
the cost of reference maintenance significantly. The cost of most-
frequently-used reference copying, such as passing references as
parameters or return values between function calls, are removed. More
advanced technique, such as GlobalMemoryFence, are used to eliminate
the memory ordering cost for a multi-processors platforms.

Easy-to-Use and Portable - Just linking with our library, you can
enjoy all of above features and the more. You can even use our library
with .NET managed code in visual C++. There is no too much
restriction, you can use template, union, bit-fields, multiple-
inheritance, object composition, and array of objects in HnxGC as
efficiency as in traditional C++. The source code is available, and
the only required for your application is a standard C++ compiler,
such as Visual C++ or GNU C++. No use of any special features of any
specific compiler, nor any platform specific system calls. Can even
run without virtual memory support. Write your garbage-collected C++
application once, and it is easy to port to a wider array of
platforms, no constraint to any specific platform vendors.

 

[Juha Nieminen]

http://hnxgc.harnixworld.com

"The author of HnxGC has filed several patents of HnxGC in the United
States and other countries. Whoever without authority makes, uses,
offers to sell, or sells any of these patented invention, within the
United States and/or other countries infringes the patent(s)."

You are claiming patent protection for something which has not been
granted a patent yet?

Besides, you should really acquaint yourself about how patents work
outside the US. You just can't patent something in the US and then claim
that using the algorithm outside the US infringes some patent law. Most
other countries do not have software patents, do not respect software
patents of other countries, and above all, even if it was a valid
patent, they allow the *use* of such patents without express permission
(even if distributing products using the patent is prohibited). Just
claiming that "you can't use this without permission" has no legal
validity. You are claiming more rights than you really have.

Good thing you didn't claim copyright prohibits people from using your
algorithms, as algorithms do not fall into the realm of copyright.

 

[Joe Seigh]

The HnxGC Libraray - an accurate, pauseless & deterministic garbage
collector for C++ application, is released at

http://hnxgc.harnixworld.com

(MD5: b96a83d0899317e732abb46a5e1f2dd5)

Features include:

Accurate - HnxGC is a fully accurate tracing garbage collector. We
don't use any tricks to guess/distinguish pointers from other data.
All effective references are identified. There is no leak of garbage
objects uncollected and all associated native resources will be
freed.

Pauseless - HnxGC come with a lock-free and block-free concurrent
collector with no need to scan root-set area. We don't need to take a
snapshot to determine application status, thus the normal execution of
application thread will never be interrupted, suspended, blocked or
forced to spin-waiting by our collector, no matter in a multi-
processors or an uni-processor environment.

Deterministic - HnxGC always executes the destructor of an object when
application program drops the last reference to the object. In
addition, application program can declare dependence rules for each
object to control the destructing ordering of cyclic garbage objects.
The system will figure out an ordering that satisfies all user-
declared rules. Thus, application programmers have more controls on
how unreachable objects are reclaimed, more compliance to RAII
(Resource Acquisition Is Initialization) design pattern, such as
closing file handle or network connection in the destructor routine of
objects.

Efficient - Even HnxGC provide deterministic reclamation feature
similiar to the one in regular reference counting algorithm, we remove
the cost of reference maintenance significantly. The cost of most-
frequently-used reference copying, such as passing references as
parameters or return values between function calls, are removed. More
advanced technique, such as GlobalMemoryFence, are used to eliminate
the memory ordering cost for a multi-processors platforms.

Easy-to-Use and Portable - Just linking with our library, you can
enjoy all of above features and the more. You can even use our library
with .NET managed code in visual C++. There is no too much
restriction, you can use template, union, bit-fields, multiple-
inheritance, object composition, and array of objects in HnxGC as
efficiency as in traditional C++. The source code is available, and
the only required for your application is a standard C++ compiler,
such as Visual C++ or GNU C++. No use of any special features of any
specific compiler, nor any platform specific system calls. Can even
run without virtual memory support. Write your garbage-collected C++
application once, and it is easy to port to a wider array of
platforms, no constraint to any specific platform vendors.

CC'ing c.p.t

I don't know what the GlobalMemoryFence is yet since that part is not
filled in yet. Generally with shared pointers you need acquire/release
semantics which can't be elided.

 

[Joe Seigh]

(sorry for the repost but it probably would help if I actually included c.p.t)

The HnxGC Libraray - an accurate, pauseless & deterministic garbage
collector for C++ application, is released at

http://hnxgc.harnixworld.com

(MD5: b96a83d0899317e732abb46a5e1f2dd5)

Features include:

Accurate - HnxGC is a fully accurate tracing garbage collector. We
don't use any tricks to guess/distinguish pointers from other data.
All effective references are identified. There is no leak of garbage
objects uncollected and all associated native resources will be
freed.

Pauseless - HnxGC come with a lock-free and block-free concurrent
collector with no need to scan root-set area. We don't need to take a
snapshot to determine application status, thus the normal execution of
application thread will never be interrupted, suspended, blocked or
forced to spin-waiting by our collector, no matter in a multi-
processors or an uni-processor environment.

Deterministic - HnxGC always executes the destructor of an object when
application program drops the last reference to the object. In
addition, application program can declare dependence rules for each
object to control the destructing ordering of cyclic garbage objects.
The system will figure out an ordering that satisfies all user-
declared rules. Thus, application programmers have more controls on
how unreachable objects are reclaimed, more compliance to RAII
(Resource Acquisition Is Initialization) design pattern, such as
closing file handle or network connection in the destructor routine of
objects.

Efficient - Even HnxGC provide deterministic reclamation feature
similiar to the one in regular reference counting algorithm, we remove
the cost of reference maintenance significantly. The cost of most-
frequently-used reference copying, such as passing references as
parameters or return values between function calls, are removed. More
advanced technique, such as GlobalMemoryFence, are used to eliminate
the memory ordering cost for a multi-processors platforms.

Easy-to-Use and Portable - Just linking with our library, you can
enjoy all of above features and the more. You can even use our library
with .NET managed code in visual C++. There is no too much
restriction, you can use template, union, bit-fields, multiple-
inheritance, object composition, and array of objects in HnxGC as
efficiency as in traditional C++. The source code is available, and
the only required for your application is a standard C++ compiler,
such as Visual C++ or GNU C++. No use of any special features of any
specific compiler, nor any platform specific system calls. Can even
run without virtual memory support. Write your garbage-collected C++
application once, and it is easy to port to a wider array of
platforms, no constraint to any specific platform vendors.

CC'ing c.p.t

I don't know what the GlobalMemoryFence is yet since that part is not
filled in yet. Generally with shared pointers you need acquire/release
semantics which can't be elided.

 

[osmium]

"The author of HnxGC has filed several patents of HnxGC in the United
States and other countries. Whoever without authority makes, uses,
offers to sell, or sells any of these patented invention, within the
United States and/or other countries infringes the patent(s)."

You are claiming patent protection for something which has not been
granted a patent yet?

Besides, you should really acquaint yourself about how patents work
outside the US. You just can't patent something in the US and then claim
that using the algorithm outside the US infringes some patent law. Most
other countries do not have software patents, do not respect software
patents of other countries, and above all, even if it was a valid
patent, they allow the *use* of such patents without express permission
(even if distributing products using the patent is prohibited). Just
claiming that "you can't use this without permission" has no legal
validity. You are claiming more rights than you really have.

Good thing you didn't claim copyright prohibits people from using your
algorithms, as algorithms do not fall into the realm of copyright.

You seem to have some hostility problems with the patent system, nothing
wrong with that. However:

It is, and has always been, standard in the USA to warn people that a patent
has been applied for. I think the lack of such a warning was a part of the
LZW fiasco a few years ago.

The OPs mention of "other countries" instead of saying "the planet" contains
a clear implication that he is speaking of *some* other countries.

Using number of countries (most) is a pitiful metric. It equates, say,
Sierra Leone with Germany. Germany is more likely to produce patents by
their own people and are thus interested in the whole notion of patents..
As I understand it, the Vatican is a country, and so is France - why treat
them the same?

 

[Chris Thomasson]

(sorry for the repost but it probably would help if I actually included
c.p.t)

[...]

Have you addressed the concerns I had:

http://groups.google.com/group/comp.lang.c++/browse_frm/thread/95007ffdf246d50e

?

 

[Chris Thomasson]

(sorry for the repost but it probably would help if I actually included
c.p.t)

[...]

Have you addressed the concerns I had:

http://groups.google.com/group/comp.lang.c++/browse_frm/thread/95007ffdf246d50e

?

Are you still using smart-pointers?

 

[Chris Thomasson]

(sorry for the repost but it probably would help if I actually included
c.p.t)

[...]

Have you addressed the concerns I had:

http://groups.google.com/group/comp.lang.c++/browse_frm/thread/95007ffdf246d50e

?

AFAICT, it seems like your using an atomic reference counting algorithm with
smart pointers. Do you need to use interlocked instructions to modify the
count? How does you reference counting technique get around prior art? I
assume that you did a full-blown patent search/feasibility check...

 

[Erik Wikström]

The OPs mention of "other countries" instead of saying "the planet" contains
a clear implication that he is speaking of *some* other countries.

Actually, if I say "within the United States and/or other countries" I
mean *all* countries, including the US, and I think that my
interpretation is quite common. This however is totally off-topic in
this group so I will say no more on the subject.

 

[Roland Pibinger]

The HnxGC Libraray - an accurate, pauseless & deterministic garbage
collector for C++ application, is released [...]
Deterministic - HnxGC always executes the destructor of an object when
application program drops the last reference to the object.

Apart from the commercial background and apart from the apparent
contradiction in 'deterministic garbage collector' this library, IMO,
touches some interesting aspects:
A future C++-like language should have deterministic destruction but
no 'delete' operator. It's mostly a task for the compiler to determine
the right scope for destruction, e.g. by escape analysis (to a lesser
extent some runtime mechanism (reference counting?) needs to be
involved). Moreover, there should be no difference in syntax between
creating objects on the 'stack' and creating them on the 'heap'. This
distinction becomes an unimportant implementation detail for the
programmer.

 

[Chris Thomasson]

(sorry for the repost but it probably would help if I actually included
c.p.t)

Why not use a simple lock-free proxy garbage collector (e.g., PDR):

http://groups.google.com/group/comp.programming.threads/browse_frm/thread/82376b7295e6ce1a

http://groups.google.com/group/comp...ch?hl=en&group=comp.programming.threads&q=PDR



? Here is a free example:

http://home.comcast.net/~vzoom/demos/pc_sample.c


This uses interlocked operations for extracting the necessary epoch
information, but its way better then rw-mutexs for protected read-size proxy
collected region. How do you beat RCU read-side performance characteristics
in general?

The proxy method has its advantages, such as the ability to plain/raw atomic
loads and stores w/ dependant load memory-barriers to access the shared
data-structures; no interlocking and #StoreLoad barriers required for
read-side critical regions. Please note that the membar mentioned is a NOP
on virtually every system out there, except the Alpha architecture:

https://coolthreads.dev.java.net/servlets/ProjectForumMessageView?forumID=1797&messageID=11068

https://coolthreads.dev.java.net/servlets/ProjectForumMessageView?messageID=11001&forumID=1797


The proxy collector allows the writers to use many different techniques,
including but definitely not limited to POSIX mutexs and lock-free
algorithms. I would consider STM to be a candidate for the writer side of a
reader pattern; its about the only thing that STM is useful for, IMHO at
least. Solving the deadlocking problem can be done with correct locking
pattern; STM is not needed for that...



How does your stuff get around prior art? Please inform us when your patent
application is published. I would like to read it as I am interested in the
way you algorithms works. I like implementation details. You mentions that
you do not make any systems calls? You get around using libc and POSIX API
correct? You don't need assembly language to do the atomic/membar stuff? I
am interested in your implementation details indeed.

 

[Mingnan G.]

I don't know what the GlobalMemoryFence is yet since that part is not
filled in yet. Generally with shared pointers you need acquire/release
semantics which can't be elided.

By downloading the source code, you will find in HNXGC_MT directory
which uses
the Global Memory Fence technology to elide acquire/release semantics
in a multi-processors environment, such as for Windows 64-bit IA64
platform. The binary code
for Windows 64-bit IA64 is also available.

 

[Mingnan G.]

I don't know what the GlobalMemoryFence is yet since that part is not
filled in yet. Generally with shared pointers you need acquire/release
semantics which can't be elided.

By downloading the source code, you will find in HNXGC_MT directory
which uses the Global Memory Fence technology to elide acquire/
release
semantics in a multi-processors environment, such as for Windows 64-
bit
IA64 platform. The binary code for Windows 64-bit IA64 is also
available.

 

[Chris Thomasson]

By downloading the source code, you will find in HNXGC_MT directory
which uses
the Global Memory Fence technology to elide acquire/release semantics
in a multi-processors environment, such as for Windows 64-bit IA64
platform. The binary code
for Windows 64-bit IA64 is also available.

You don't make systems calls (e.g., no POSIX), you don't tie to a platform
(e.g., no assembly language) and your GlobalMemoryFence is 100% portable?

Are you tracking quiescent state epochs? How do you get around RCU, SMR,
vZOOM and other prior art? I don't have time to read thought a lot of
source-code right now. Can you please explain some details without me having
to read source-code? We have discussed a lot of ways to get around explicit
memory barriers here in cpt. Can you give some details on how your is
fundamentally different that my free proxy collector example, or Joes
SMR+SMR? You don't need acquire/release? Really? You have to be tracking
something to ensure stores don't escape the drop-to-zero condition in
reference counting in general? Do tell. Please? Thanks for your time.

 

[Arnold Hendriks]

Are you tracking quiescent state epochs? How do you get around RCU, SMR,
vZOOM and other prior art? I don't have time to read thought a lot of

Either way, being outside the US, he may not care about prior art

 

[hyc]

You don't make systems calls (e.g., no POSIX), you don't tie to a platform
(e.g., no assembly language) and your GlobalMemoryFence is 100% portable?

Are you tracking quiescent state epochs? How do you get around RCU, SMR,
vZOOM and other prior art? I don't have time to read thought a lot of
source-code right now. Can you please explain some details without me having
to read source-code? We have discussed a lot of ways to get around explicit
memory barriers here in cpt. Can you give some details on how your is
fundamentally different that my free proxy collector example, or Joes
SMR+SMR? You don't need acquire/release? Really? You have to be tracking
something to ensure stores don't escape the drop-to-zero condition in
reference counting in general? Do tell. Please? Thanks for your time.

You'd rather read a vague patent application written in legalese than
actual source code? Talk about a masochist. What makes you think there
would ever *be* a patent application? What makes you even think
software patents are in any way a proper use of anyone's time? By the
way, patents generally can't be applied for after publication. If this
code is already available for download, then there won't be any patent
application.

 

[hyc]

What makes you think there
would ever *be* a patent application?

Never mind. The web site says patent-pending. Sigh...

 

[Mingnan G.]

would ever *be* a patent application? What makes you even think
software patents are in any way a proper use of anyone's time? By the

You worry too much. For a non-commercial educational purpose, you can
apply
for a *FREE* license for this software. See follows:

Permission to use, copy and distribute this software and its
documentation
for a non-commercial educational purpose can be granted free
by electronic registration via hnxgc.harnixworld.com, provided that
this
copyright notice appears in all copies.

 

[Juha Nieminen]

By the
way, patents generally can't be applied for after publication. If this
code is already available for download, then there won't be any patent
application.

That my be true in Europe but not in the US.

 

[Matthias Buelow]

You worry too much. For a non-commercial educational purpose, you can
apply
for a *FREE* license for this software. See follows:

[blah]

If your development is so breathtakingly innovative and of general
applicability to C++ programming, why don't you make it available to the
whole programming community as free software under a liberal license.

Instead of spamming this newsgroup with your product advertisement and
annoying everyone with "software patent" nonsense.