Inserting In a List

[markspace]

final Point p = new Point(0, 0);
p.move(1, 1);

Are you really trying to say that you believe that the final keyword has
made p immutable,

Nope, p is clearly mutable here.

public class A {
final int b = 123;
}

OK, as far as it goes. But see below.

But of course, again, you cannot make an mutable OBJECT immutable simply by
creating a reference to it that is decorated with final.

Yup, you can. This class is also immutable:

public class Stooges {
private final ArrayList<String> stooges = new ArrayList<>(3);
{ stooges.add("Larry"); stooges.add("Curly"); stooges.add("Moe");}

public String getStooge( int stooge ) {
if( stooge < 1 || stooge > 3 ) throw new IllegalArgumentException();
return stooges.get( stooge-1 );
}
}

Now as long as I haven't made some syntax or other simple error, all
instances of Stooges are immutable under the section of the JLS I
quoted. More over, each one is thread safe in all circumstances and
does not need synchronization to make it thread safe.

You may know this yourself, but the way you wrote the bit I quoted made
is sound like final fields have no special semantics associated with
them with respect to immutable objects (like the stooges ArrayList I
used above), when in fact they do. Although not in the fashion you
implied with p above, of course.

Again, I'm pretty certain that you already know all of the above and we are
just having a communication breakdown.

I think so.

 

[Joerg Meier]

Yup, you can. This class is also immutable:

public class Stooges {
private final ArrayList<String> stooges = new ArrayList<>(3);
{ stooges.add("Larry"); stooges.add("Curly"); stooges.add("Moe");}

public String getStooge( int stooge ) {
if( stooge < 1 || stooge > 3 ) throw new IllegalArgumentException();
return stooges.get( stooge-1 );
}
}

But it's immutable because you don't expose mutable functionality, not
because of the final keyword. Let me make a small alteration that will make
your class mutable, without removing the final keyword:

public class Stooges {
private final ArrayList<String> stooges = new ArrayList<>(3);
{ stooges.add("Larry"); stooges.add("Curly"); stooges.add("Moe");}

public String getStooge( int stooge ) {
if( stooge < 1 || stooge > 3 ) throw new IllegalArgumentException();
return stooges.get( stooge-1 );
}

public ArrayList<String> getStooges() {
return stooges;
}
}

There, and suddenly it's mutable.

Now as long as I haven't made some syntax or other simple error, all
instances of Stooges are immutable under the section of the JLS I
quoted. More over, each one is thread safe in all circumstances and
does not need synchronization to make it thread safe.

Yours would be immutable with or without the final keyword. It's kind of a
bad example, because ArrayList itself is mutable. Should have wrapped it in
Collections.unmodifiableList at least, but of course then it could still
have mutable contents (although of course not in the example, as String is
both immutable and final).

You may know this yourself, but the way you wrote the bit I quoted made
is sound like final fields have no special semantics associated with
them with respect to immutable objects (like the stooges ArrayList I
used above), when in fact they do. Although not in the fashion you
implied with p above, of course.

final can be used to create a class that is immutable, but so can other
Java mechanics (such as private fields with no setter). While final
certainly lends itself to design of immutable classes, there really aren't
any special semantics associated with it any more than with the private
keyword.

I think so.

Yeah, I figured halfway into my post that perceived misconception on your
part was too severe for it to actually be one. Nevertheless it seems a
worthwhile topic to discuss and maybe it will help someone else reading it
understand things better.

Liebe Gruesse,
Joerg

 

[Arved Sandstrom]

You can feel free to say whatever you want, but lets be realistic: the
majority of people will say "Java has" for stuff in the JCL, and "Java
doesn't have" for stuff not in the JCL. And I am 99% certain that if I had
asked you any of the examples above, you would have said "No, Java doesn't
have a val data type", and you would have says "Yes, Java has a hash map,
it's java.util.HashMap".

You can be pedantic all you want, but I would argue that "stuff in the JCL"
is the definition used by the vast majority of people and really the only
one that makes much sense.

[ SNIP ]

I'm probably not most people. I can do very little of my professional
Java work using just the Java language and only official Java platform
libraries. So I value 3rd party offerings very highly.

As for the questions, what are Java primitives if not value types? And I
very likely wouldn't say that Java has a hash map, honestly; it's too
ingrained in me that "Java" is the language only. I think similarly with
every other language + platform I can think of: C# is a .NET language,
the .NET framework is actually what supplies the libraries. Haskell is a
language, GHC and other environments supply many libraries. Etc.

But I'll concede that I'm not the vast majority of people. A lot of
people in that vast majority have also been often wrong when they
conflate an API supplied by the Java platform and an implementation
thereof, and happily believe that "Java" is providing all of it.

AHS

 

[Joerg Meier]

You can feel free to say whatever you want, but lets be realistic: the
majority of people will say "Java has" for stuff in the JCL, and "Java
doesn't have" for stuff not in the JCL. And I am 99% certain that if I had
asked you any of the examples above, you would have said "No, Java doesn't
have a val data type", and you would have says "Yes, Java has a hash map,
it's java.util.HashMap".
You can be pedantic all you want, but I would argue that "stuff in the JCL"
is the definition used by the vast majority of people and really the only
one that makes much sense.

[ SNIP ]

I'm probably not most people. I can do very little of my professional
Java work using just the Java language and only official Java platform
libraries. So I value 3rd party offerings very highly.

Using a lot of JavaEE, I'm right there with you. But I wouldn't say
RestEASY or Jackson are part of Java any more than I would say Firefox is
part of Windows.

As for the questions, what are Java primitives if not value types? And I

val data types != value types, a val type is a variable type that can be
used like:

for (val file : fileList) { ... // val is of type File here }

Basically an inferred type.

very likely wouldn't say that Java has a hash map, honestly; it's too
ingrained in me that "Java" is the language only. I think similarly with

So you would say that Java has ArrayMap, but not a hash map. You need to
pick one side to disagree with me on, it seems ;-)

Liebe Gruesse,
Joerg

 

[markspace]

Yours would be immutable with or without the final keyword.

No no no. This is my point. The final keyword has special semantics
associated with it in that particular case. It works a bit like the
volatile keyword: all writes to that point are made visible. In the
case of a private final field, the writes are made visible to ALL
THREADS in the system. THAT is what makes instances of the class
Stooges immutable.

That's why no synchronization is needed. Which is huge, conceptually.
I'll stop there because I think this may be the whole point of
misunderstanding here.

 

[Arne Vajh?j]

You can feel free to say whatever you want, but lets be realistic: the
majority of people will say "Java has" for stuff in the JCL, and "Java
doesn't have" for stuff not in the JCL. And I am 99% certain that if I
had
asked you any of the examples above, you would have said "No, Java
doesn't
have a val data type", and you would have says "Yes, Java has a hash map,
it's java.util.HashMap".

You can be pedantic all you want, but I would argue that "stuff in the
JCL"
is the definition used by the vast majority of people and really the only
one that makes much sense.

[ SNIP ]

I'm probably not most people. I can do very little of my professional
Java work using just the Java language and only official Java platform
libraries. So I value 3rd party offerings very highly.

I guess most do, but that does not make anything part of Java.

As for the questions, what are Java primitives if not value types? And I
very likely wouldn't say that Java has a hash map, honestly; it's too
ingrained in me that "Java" is the language only. I think similarly with
every other language + platform I can think of: C# is a .NET language,
the .NET framework is actually what supplies the libraries. Haskell is a
language, GHC and other environments supply many libraries. Etc.

But I'll concede that I'm not the vast majority of people. A lot of
people in that vast majority have also been often wrong when they
conflate an API supplied by the Java platform and an implementation
thereof, and happily believe that "Java" is providing all of it.

I believe there are precedence for that the owner of the
Java trademark may sue someone using the name Java for something
not having all the classes in the Java library (SUN vs MS).

So I would say that:

Java = Java language + Java library + JVM

Arne

 

[Arved Sandstrom]

On Wed, 03 Apr 2013 18:09:36 -0300, Arved Sandstrom wrote:
If we're going to be pedantic I might as well add that I wouldn't myself
say that Java has ArrayLists or HashMaps either. I consider "Java" to be
the language. If we're going to talk official libraries you'd have to
refer to a specific version of J2SE/Java SE or J2EE/Java EE, for example.
You can feel free to say whatever you want, but lets be realistic: the
majority of people will say "Java has" for stuff in the JCL, and "Java
doesn't have" for stuff not in the JCL. And I am 99% certain that if I had
asked you any of the examples above, you would have said "No, Java doesn't
have a val data type", and you would have says "Yes, Java has a hash map,
it's java.util.HashMap".
You can be pedantic all you want, but I would argue that "stuff in the JCL"
is the definition used by the vast majority of people and really the only
one that makes much sense.

[ SNIP ]

I'm probably not most people. I can do very little of my professional
Java work using just the Java language and only official Java platform
libraries. So I value 3rd party offerings very highly.

Using a lot of JavaEE, I'm right there with you. But I wouldn't say
RestEASY or Jackson are part of Java any more than I would say Firefox is
part of Windows.

As for the questions, what are Java primitives if not value types? And I

val data types != value types, a val type is a variable type that can be
used like:

for (val file : fileList) { ... // val is of type File here }

Basically an inferred type.

OK, I misconstrued your use of the term "val". Sure, like "var" and
"val" in various languages. Yes, we don't have that in Java.

So you would say that Java has ArrayMap, but not a hash map. You need to
pick one side to disagree with me on, it seems ;-)

Liebe Gruesse,
Joerg

I used the term "Java" initially because I do recognize that most folks
use it exactly the way you say, even though I don't. But you'll recall
that very quickly after I made my distinction.

So truthfully I'd have to say that Java has neither, not by my usage.

I don't actually beat people up over this, you know. It doesn't
exactly usually come up, someone just asks does anyone know a class or
classes that does such and such, and someone else suggests a library. If
it's 3rd party they'll say so, otherwise they just usually say it's
package such-and-such.

AHS

 

[Arne Vajh?j]

Are you serious, Arne?
Very.

Did you read the section I linked to? I didn't
quote the whole thing, it would be immense. I just quoted one line to
show that the section did talk about immutability, not to definitively
establish all the ins-and-outs of immutability in the JLS. There's no
point in me copying what you can read yourself.

JLS referring to immutability is utterly irrelevant.

The question is whether JLS defines it.

Feel free to quote where it defines it.

Or stop making claims.

Honestly I'm shocked at your response and I think you're missing the
point by a wide margin. Are you trying to tell me that final fields are
not involved in immutability in Java?

I was just pointing out that what you quoted from JLS did not
support your claim that JLS had a formal definition of immutability.

I find it a bit difficult to see why you think that implies
"final fields are not involved in immutability in Java".

Arne

 

[Joerg Meier]

No no no. This is my point. The final keyword has special semantics
associated with it in that particular case. It works a bit like the
volatile keyword: all writes to that point are made visible. In the
case of a private final field, the writes are made visible to ALL
THREADS in the system. THAT is what makes instances of the class
Stooges immutable.

Now I'm to being confused by you. final prevents any writes other than the
initial one. That initial write is not synchronized to other threads. If
you let an object instance get out that isn't fully constructed, then you
will get the usual synchornization issues, final or not. Don't believe me ?

Guess what this will print out:

public class FinalTest {
public static class Test {
public final String bla;

public Test() {
new Thread(new Runnable() {
public void run() {
try {
Thread.sleep(200);
} catch (final InterruptedException e) {}
System.out.println(bla);
try {
Thread.sleep(1000);
} catch (final InterruptedException e) {}
System.out.println(bla);
}
}).start();
try {
Thread.sleep(1000);
} catch (final InterruptedException e) {}
bla = "1234";
}
}

public static void main(final String[] args) {
final Test test = new Test();
}
}

If I misunderstood, and you believe that structural changes to the
ArrayList would be visible to all threads, then you are still wrong, but
you're going to have to write this test case as I restrict myself to one
test case per post

That's why no synchronization is needed. Which is huge, conceptually.
I'll stop there because I think this may be the whole point of
misunderstanding here.

The mere use of final does not remove the need for synchronization. Nor
does the mere lack of it dictate a need. The reason synchronization is not
needed with proper immutability is an effect from what final does - because
it can only be assigned once, once it is you can then let everyone play
with it, because you dont NEED to worry about writes - there will be none.

Liebe Gruesse,
Joerg

 

[markspace]

I was just pointing out that what you quoted from JLS did not
support your claim that JLS had a formal definition of immutability.

But I don't care if you believe. The link is for your sake.

I find it a bit difficult to see why you think that implies
"final fields are not involved in immutability in Java".

Er, I'm saying the opposite.

 

[Joerg Meier]

OK, I misconstrued your use of the term "val". Sure, like "var" and
"val" in various languages. Yes, we don't have that in Java.

Actually, we do - if you count third party libraries ;-)

So truthfully I'd have to say that Java has neither, not by my usage.

Then we just use the term differently. I'm alright with that.

Liebe Gruesse,
Joerg

 

[Arne Vajh?j]

JLS referring to immutability is utterly irrelevant.

The question is whether JLS defines it.

Feel free to quote where it defines it.

Or stop making claims.


I was just pointing out that what you quoted from JLS did not
support your claim that JLS had a formal definition of immutability.

I find it a bit difficult to see why you think that implies
"final fields are not involved in immutability in Java".

But now you raise the question, then final is only slightly
involved in immutability in Java.

If is neither sufficient nor necessary to make them
immutable.

Bloch recommends using final for immutables to:
- express intention
- work better with the Java memory model

Arne

 

[Arne Vajh?j]

But I don't care if you believe. The link is for your sake.

So it is there but you just don't want to provide the quote yourself.

Do you think that sounds credible?

Er, I'm saying the opposite.

Yes. But you you seemed to imply that I meant it based
on the JLS thing.

Arne

 

[Arne Vajh?j]

No no no. This is my point. The final keyword has special semantics
associated with it in that particular case. It works a bit like the
volatile keyword: all writes to that point are made visible. In the
case of a private final field, the writes are made visible to ALL
THREADS in the system. THAT is what makes instances of the class
Stooges immutable.

That's why no synchronization is needed. Which is huge, conceptually.

It can be very important in multithreaded context.

But it is not what makes a class immutable.

Arne

 

[Arne Vajh?j]

[...]
I believe in using "final" pretty often as it will immediately indicate
which local variables are constant for a method call and which are
modified all the time. [...]

De gustibus non disputandum est, but I think "final" should
be reserved for things that *mustn't* change, and shouldn't just
be pasted on to anything that happens to remain constant in the
code's current incarnation. When considering a change to some
code I might see

Thing thing = getThing();
// ... code that doesn't happen to change `thing'

I am so used to using "final" that this immediately makes me wonder why
it's not final - did the author intend to not change it, forget to
change it or forgot the "final"?

Many years ago the fathers of Java designed it so that default was
var and the final modifier could change that.

They could have decide to make val default and have a nonfinal
modifier that could change that.

You are trying to code as if they had picked the second.

Arne

 

[Arne Vajh?j]

On 4/2/2013 8:20 PM, Arne Vajh?j wrote:
On 4/2/2013 8:04 PM, Joerg Meier wrote:
On Tue, 2 Apr 2013 22:52:20 +0000 (UTC), Martin Gregorie wrote:

06 PM, Martin Gregorie wrote:
[...]
Its also not clear to me whether the OP is expecting some form of
sorted list of filenames. If he is expecting that, it would be
best to
use a TreeMap<String> rather than an ArrayList<String> to store the
filenames.
Is there a reason to prefer TreeMap (or other SortedMap) over
accumulate-disordered-and-sort-afterward?
I think so, yes, because none of File's list() and listFiles()
methods
guarantee the order of the returned files. By using TreeMap or
equivalent
the OP gets the sort for free, should it be required.

For free ? The cost is just distributed amongst the insert calls,
and is
likely considerably higher than with an unsorted list that has a
single
sort call once it is filled.

It is not that obvious to me that:

n O(1) + 1 O(nlogn) is that much faster than n log(n)

By design, O() obscures all the coefficients. If you were
to say that n*log(n) and 9999999999999999999999999999*n*log(n)
are both O(n*log(n)) you would be right -- but if you were to
claim the former was not "that much faster" than the latter you
would be wrong by a factor of 9999999999999999999999999999.

Yes.

But given same big-O I would expect some solid reasons for a
big difference in coefficients before I assume a big difference
in performance.

... and that's the gist of my question: It seems to me likely
that the actual time to sort an ArrayList of large-ish N size will
be less than the time to build a TreeMap (BTW, Martin probably
meant TreeSet) of the same N items. Argument: The TreeSet expends
effort in keeping itself always sorted all the time, while the
ArrayList has the freedom to be disordered up until the end, and
then to impose an ordering just once. The ArrayList is asked to
present one sorted version of N items, while the TreeSet must
offer sorted versions of 1,2,3,...,N items. If the intermediate
orderings are not required, I don't see much reason to compute them.

I can follow you so far that TreeSort is likely a bit slower
than the ArrayList sort.

But I can not see any reason to expect a big difference.

It is fundamentally the same divide and conquer principle
applied.

The original assertion is "it would be *best* [emphasis mine]
to use a TreeMap<String> [sic] rather than an ArrayList<String>".
I'm not claiming that the difference is "big," nor even that the
difference is "important" -- for reasonably-sized directories, at
any rate. What I'm questioning is "best."

But I did not comment on Martin's "best".

I commented on Joerg's "likely considerably higher".

Arne

 

[markspace]

That initial write is not synchronized to other threads.

Yes it is! (Not immediately synchronized, at the end of the ctor.)
Read the JLS, besides the part I quoted above:

<http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.5.1>

"Let o be an object, and c be a constructor for o in which a final field
f is written. A freeze action on final field f of o takes place when c
exits, either normally or abruptly....

Given a write w, a freeze f, an action a (that is not a read of a final
field), a read r1 of the final field frozen by f, and a read r2 such
that hb(w, f), hb(f, a), mc(a, r1), and dereferences(r1, r2), then when
determining which values can be seen by r2, we consider hb(w, r2). (This
happens-before ordering does not transitively close with other
happens-before orderings.) "

That's as clear as mud, but what it means is that objects referenced by
final fields, and all writes to those objects, are made visible at the
end of the object's ctor.

If
you let an object instance get out that isn't fully constructed, then you
will get the usual synchornization issues, final or not. Don't believe me ?

This is true. If the final field object escapes from the enclosing
class, or any writes are made after the object is constructed, then both
immutability and thread-safety are broken.

If I misunderstood, and you believe that structural changes to the
ArrayList would be visible to all threads, then you are still wrong,

In the second example you gave where the reference to 'stooges' leaves
the enclosing class, it is definitely neither immutable nor thread-safe.

The mere use of final does not remove the need for synchronization.

Yes it does! That was explicitly stated in the very short bit I quoted
at the beginning of this whole mess.

Nor
does the mere lack of it dictate a need.

No. 'final' is special here.

The reason synchronization is not
needed with proper immutability is an effect from what final does - because
it can only be assigned once, once it is you can then let everyone play
with it, because you dont NEED to worry about writes - there will be none.

No, you still need to, at a low level, insert a memory barrier to make
those writes visible. You'd need to use synchronization or a volatile
variable or some other synchronization in Java, or you could see a
partially constructed object. Just like any regular object that doesn't
use final or volatile fields.

Also, go read Java Concurrency in Practice by Brian Goetz. He covers
this in some detail (complete with Stooges example).

 

[markspace]

Yes. But you you seemed to imply that I meant it based
on the JLS thing.

No, I was replying to Joerg.

 

[markspace]

But now you raise the question, then final is only slightly
involved in immutability in Java.

If is neither sufficient nor necessary to make them
immutable.

final is necessary. It is not sufficient (you also have to not mutate
the object in question after the enclosing object's ctor exits). I'm
pretty sure the field must also be explicitly private. (Implicitly
might not be enough to satisfy what ever escape analysis the Java
compiler does.)

Bloch recommends using final for immutables to:
- express intention
- work better with the Java memory model

Read Java Concurrency in Practice. That's what I'm referring too.

 

[Arne Vajh?j]

No, I was replying to Joerg.

Hmm.

You replied to a post by me and only quoted me.

A bit difficult to guess that you were actually replying to Joerg.

Arne