Optimizing Java using D

[Dmitry Olshansky via Digitalmars-d]

06-Jul-2014 07:19, Wanderer пишет:
> On Saturday, 5 July 2014 at 16:03:17 UTC, Dmitry Olshansky wrote:
>> There are trade-offs. The world is not black and white and I don't
>> follow 'one rule everywhere'.
>
> This is not a trade-off at all. You suggested to keep database records
> linearly, with space gaps between records to support "tiny updates".
> Without serious updates, this is major waste of space. With them, your
> design won't save the day, because any gap will be eventually consumed
> and without fragmentation/reordering, the storage will fail.
>

Strawman.

> FYI, nowaday popular databases aren't designed this way, exactly for the
> reasons I described above. All databases I worked with (MySQL, Oracle
> and Firebird) hold records in very compact way, without a single byte
> gaps, with ability of fragmentation, and without total physical
> ordering. So at least designers of these DBMS have agreed that your
> design is not practical.

Well they got to store a link somewhere, right? That's already 4 or 8 
bytes of "gap" to have in case of adding an extra field. In fact taking 
a peek at typical DB file I see LOTS of zeros in between real data.

Again - linked vs linear *is* a tradeoff, and it's taken not once and 
for all. It's good to have ability to choose, but from your posts it's 
apparent you don't need choice and just fine without it.

>> Pointers are perfectly fine as long as there is no pointer arithmetic.
>
> Wrong. Merely holding a pointer (i.e. a physical address) is unsafe
> already.

Anyhow your definition of unsafe is hard to grasp.

> Non-deep serialization, or any other "preservation" of such a
> struct and  GC is unable to keep the track of pointers.

You are no better with references in these kind of circumstances. GC is 
able to track references/pointers, that's its job.

>
>> Which is hopelessly admitting defeat. A pair may have non-trivial
>> comparator. And a minor step beyond that such as a pair of double and
>> integer and it fails completely.
>
> I said above: in any non-trivial case, use classes instead of
> overly-clever structures.

Why? I understand that where you are coming from there is simply no 
choice and hence the argument of 'just use this' holds water.

And this is nothing clever in a simple hierarchical composition of 
records stored in one piece of memory contiguously.

> And if you really, really need premature
> optimization, there is java.nio and buffers. Create ByteBuffer (direct
> one if you need super optimized solution) and treat slices of it as
> "structs".

It would be inferior to structs in many ways, including really slow 
binary serialization to the buffer step (Java has no way to just 
bit-blitting integers to byte array).

BTW I fail to see how NIO would instantly imply super optimized solution 
esp as it would require reconstructing fields from bytes on each access.

> That's possible and easy to implement, but really not needed
> in practice because all you get is 0.1% of memory saving and no gain in
> speed.

Since in Java you really can't measure this stuff (as there is no way to 
lay things out in memory) you would excuse me to not trust on this one.
Storing extra reference + an unused monitor field + vtable per a pair of 
2 integers is about 50% memory wasted.

>
>> And there Java-style indirection-happy classes "shine". For instance
>> modeling any complex stuff with classes alone would lead to things like:
>> House--reference->Bedroom---reference-->Bed--reference-->Pillow
>>
>> Which is incredible waste of memory and speed on something so simple.
>
> That's not complex. That's very simple.

Oh, sure now I see let's discard things that don't seem to fit.
It's a common knowledge that Java doesn't implement composition 
properly, the only choice provided is delegation (i.e. keeping a 
reference instead of actually containing an object). There is simply no 
argument that's going to prove that "you really don't need composition".

> It would become slightly more
> complex if all house parts implemented the same root interface and basic
> operations, like examining what's around and finding an object given by
> its path or properties, or throwing an extra pillow or two onto the same
> bed. All that is just a dream for structs.

Again your ignorance of what a struct could do shows. They could have 
methods just fine. C++ std::vector is a struct after all, so an extra 
pillow goes just fine.

More over using such data structure with references everywhere ruins 
performance a topic you suddenly started to dismiss.

>> Copy constructors or in D parlance postblits. There is also CoW and
>> whatnot. In fact swap doesn't create a copy in D, it just does a
>> bitwise swap in-place.
>
> And here we have a tough choice for structs with pulled subdata "for
> efficiency": either assignment operator copies that data too (making
> routines like sort to perform horribly slow), or they perform only
> shallow copy, causing undue sharing of data and violating the whole
> struct "value" philosophy.

Again - sort doesn't copy values at all, it swaps. And there are nice 
ways to design copy semantics like CoW.

There is a reason why Java String is now eagerly copied behind the 
scenes - as it's now (internally) using small string optimization 
instead of copy-on-write. It's funny how only JVM can do things on this 
"level of structs" in Java.

>> Disagree - the moment a cache line is loaded it doesn't matter how
>> much you read in this line. Even a tiny read missing a cache is paid
>> in full.
>
> But the amount of these "missed reads" is low, so less amount of cache
> is invalidated. CPU cache is not a single page that gets invalidated as
> a whole, it's more like many small subpages, each of them is treaten
> individually.
>

I know what a CPU cache looks like.

> If you're really into the low-level mumbo jumbo, here are two more
> aspects for you to consider.
>
> 1. Since indirection does not require the object contents to be moved
> around while sorting, these objects can be read into cache once and
> never invalidated later - unlike "right in place" structs which
> invalidate CPU cache each time a swap is performed. That is a huge cache
> win already.

Plain wrong. Again seeing you have strong Java background, isn't 
particularly surprising.

> 2. Don't forget that new objects are created in eden space in Java -
> which is essentially the stack area. Very fast, compact, sequential
> memory. If your array fits in eden (and that's surely true for the
> forest problem this thread has started from), then allocating array of
> objects is essentially the same as allocating array of structs: object
> contents aren't "scattered in memory" but are located one-after-one
> without gaps between them.

Nobody told that an array is constructed in one pass or anything like 
that. There may easily (and in Java - surely) allocation in between. 
Just scratching the surface of how weak this argument is.

> That greatly aids caching as well.

Suddenly you too seem to understand that sequential storage aids CPU caches.

 > The main
> difference between eden and "array of structs" is that the allocation of
> the former never fails (assuming there's enough memory), only gets
> slightly slower in the worst case, and allocation of the latter can fail
> because "stack overflow error"

Ignorance.

> or "too much memory fragmentation oops",
> even if there's enough free memory.

Now this makes sense but not enough to prove that "references are 
ultimately better" or any other general statement.

>> And the only thing worse then copying a large file is copying a large
>> file fragmented in tiny splinters.
>
> You surely meant "reading" here, not "copying". Copying large fragmented
> file is as slow as copying large unfragmented file, because writing
> operations are the bottleneck here.

Sequential writes are okay, seeking each block isn't.

-- 
Dmitry Olshansky