You are viewing a plain text version of this content. The canonical link for it is here.
Posted to users@tomcat.apache.org by Lyallex <ly...@gmail.com> on 2012/11/08 14:35:55 UTC

This is just plain ... odd.

Java 1.6
Tomcat 6.0.35
Ubuntu Linux 12.04

I thought about posting this to a Java list but I can't
reproduce it 'standalone' so I thought I'd have a go here.

It's quite long and involved...

I have a web application that lists items for sale by category

I have a facade that publishes a method that contracts to return
a list of categories ordered alphabetically
The category 'Miscellaneous' is required to be appended to the end of the
list.

My facade calls out to a database server that returns a List<Category>
in random order. I then call collections.sort on the list and return the
result.

I've been messing around with various things and I have come up against a
very
strange problem.

One way of satisfying the contract is to write the Category class as follows
I'm not suggesting this is in any way acceptable industrial strength
code, I'm doing it to illustrate a point.

public class Category implements Comparable<Category>{

private Integer categoryId = 0;
private String category = "";

   @Override
   public int compareTo(Category c) {
      if(category.equals("Miscellaneous")){
      return 1;
   }
   else{
      return category.compareTo(c.category);
   }
}

etc

If I test this by running a client of the facade
I get the expected results, the list is ordered as required with
"Miscellaneous" on the end

However, and here's the thing, When my app starts
an initialisation servlet runs, calls the facade method
and puts the resulting List on the application context.
When I render the list via a custom tag the list has
in some way been altered so that the String
"Miscellaneous" is in it's 'natural' position
not what I want at all.

I have tried everything I can think of to reproduce this behaviour
in a standalone Java program but the list is always returned
as required. When I call the method from a servlet the list is always
returned
in it's natural order, I know collections.sort is being executed as
the list is in alpha order, it's almost as if the comparator is being
replaced in some way

I have no servlet filters or any other code 'in the way' between the facade
and the initialization servlet.

Any ideas ?

TIA

Lyallex

Re: This is just plain ... odd.

Posted by Lyallex <ly...@gmail.com>.
> > I have a facade that publishes a method that contracts to return a
> > list of categories ordered alphabetically
>
> All problems in computer science can be solved by another layer of
> abstraction. Sure you can't fit a Proxy to a Service in there?
>
>
Hmm an oldie but goodie we can discuss software analysis and design if you
like
but it's a bit OT.


> [snip]
>


> What does that "custom tag" do? A beer says it sorts something. Or,
> maybe you have some silly client-side process that sorts the entries
> after they are loaded into the browser.
>

Well I quite like Wadworth 6X I'll give you my paypal account address and
you can deposit £3.30 :-))
I can assure you I'm quite familiar with my own code and no secondary sort
is going on.

As succinctly as possible

MySQL returns results sorted by primary key by default AFAIAA
no explicit sorting is done in the database access code

/* Category server (database access) */
public List<Category> getCategories(Connection conn) throws
CategoryServerException{
String sql = "select * from Category";

populate list then return it NO SORTING

/* facade deals with transactional connections etc*/
public List<Category> getAllCategories() throws CategoryException
CategoryServer categories = new CategoryServer();
allcats = categories.getCategories(conn);
Collections.sort(allcats);

/* Initialization servlet */
CategoryFacade cats = new CategoryFacade();
List<Category> categories = cats.getAllCategories();
getServletContext().setAttribute(WebConstants.ALPHACATS, categories);

/* CategoryWriter custom tag */
List<Category> cats =(List<Category>)
pageContext.getServletContext().getAttribute(WebConstants.ALPHACATS);
Iterator<Category> iter = cats.iterator();
Category c = null;
StringBuffer buf = new StringBuffer();
     while(iter.hasNext()){
           //build the output
//output it

That's it, really, there is no more

I need to get to the bottom of this as it's bugging the hell out of me
a pound to a penny says it's something simple/stupid. I'll try what you
suggest re wrapping the collection

Thanks

Lyallex

Re: This is just plain ... odd.

Posted by Christopher Schultz <ch...@christopherschultz.net>.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Lyallex,

On 11/8/12 8:35 AM, Lyallex wrote:
> I thought about posting this to a Java list but I can't reproduce
> it 'standalone' so I thought I'd have a go here.

There's something to that "can't reproduce it standalone" that you
should be worried about.

> I have a facade that publishes a method that contracts to return a
> list of categories ordered alphabetically

All problems in computer science can be solved by another layer of
abstraction. Sure you can't fit a Proxy to a Service in there?

> My facade calls out to a database server that returns a
> List<Category> in random order. I then call collections.sort on the
> list and return the result.
> 
> [ ... ]
> 
> If I test this by running a client of the facade I get the expected
> results, the list is ordered as required with "Miscellaneous" on
> the end
> 
> However, and here's the thing, When my app starts an initialisation
> servlet runs, calls the facade method and puts the resulting List
> on the application context. When I render the list via a custom tag
> the list has in some way been altered so that the String 
> "Miscellaneous" is in it's 'natural' position not what I want at
> all.

What does that "custom tag" do? A beer says it sorts something. Or,
maybe you have some silly client-side process that sorts the entries
after they are loaded into the browser.

> I have tried everything I can think of to reproduce this behaviour 
> in a standalone Java program but the list is always returned as
> required. When I call the method from a servlet the list is always 
> returned in it's natural order, I know collections.sort is being
> executed as the list is in alpha order, it's almost as if the
> comparator is being replaced in some way

Are you using Collections.sort() or are you using a sorted collection?
If you are calling Collections.sort() then the list is sorted once and
it can be mutated. If you have a sorted list, then the comparator
could conceivably be "replaced" (but really only by creating a new
Collection).

> I have no servlet filters or any other code 'in the way' between
> the facade and the initialization servlet.

Sounds like the problem is between the application scope and the page.
Custom tag? Secondary sort?

Simple test that doesn't require you to read any of your own code:

Wrap the sorted collection in the application scope with
Collections.unmodifiableList(sortedList). Now you'll get an exception
with a stack trace whenever any code tries to re-sort it.

- -chris
-----BEGIN PGP SIGNATURE-----
Version: GnuPG/MacGPG2 v2.0.17 (Darwin)
Comment: GPGTools - http://gpgtools.org
Comment: Using GnuPG with Mozilla - http://www.enigmail.net/

iEYEARECAAYFAlCcNB4ACgkQ9CaO5/Lv0PDLuACgp/C8BkyI0cPOY5YoiwlJHnwe
td0AniTAY+GDt1h1cI45Czj9VMqLuu7U
=HvRr
-----END PGP SIGNATURE-----

---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@tomcat.apache.org
For additional commands, e-mail: users-help@tomcat.apache.org


Re: This is just plain ... odd.

Posted by Russ Kepler <ru...@kepler-eng.com>.
On Thursday, November 08, 2012 10:05:43 AM DJohnson@desknetinc.com wrote:
> 
> This is closer, but still doesn't work correctly if two "Misc" categories
> are being compared, or one "Misc" category is compared to itself.
> Try:
> 
> @Override
> public int compareTo(Category c) {
>         if(category.equals("Miscellaneous")) {
>                 if(category.equals(c.category) return 0; // correctly
> handle equality.
>                 else return 1;
>         } elseif (c.category.equals("Miscellaneous")) {
>                 return -1;
>         } else {
>                 return category.compareTo(c.category);
>         }
> }

You're right for the general case of compare(), but in my defense I'd like to 
say that merge sort will never compare the same object and the list was 
constrained to one special object, so in this case it'd work for the sort.

But it's likely better to handle the general case "just in case" someone other 
than the sort uses the compare() so your comment is well taken.  Nothing like 
fixing up one bad behaviour only to replace it with some more obscure one.


---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@tomcat.apache.org
For additional commands, e-mail: users-help@tomcat.apache.org


Re: This is just plain ... odd.

Posted by DJ...@desknetinc.com.
Russ Kepler <ru...@kepler-eng.com> wrote on 11/08/2012 09:22:41 AM:

> From: Russ Kepler <ru...@kepler-eng.com>
> To: Tomcat Users List <us...@tomcat.apache.org>, 
> Date: 11/08/2012 09:23 AM
> Subject: Re: This is just plain ... odd.
> 
> On Thursday, November 08, 2012 01:35:55 PM Lyallex wrote:

> > I have tried everything I can think of to reproduce this behaviour
> > in a standalone Java program but the list is always returned
> > as required. When I call the method from a servlet the list is always
> > returned
> > in it's natural order, I know collections.sort is being executed as
> > the list is in alpha order, it's almost as if the comparator is being
> > replaced in some way
> >
> > I have no servlet filters or any other code 'in the way' between the 
facade
> > and the initialization servlet.
> >
> > Any ideas ?

> I'm not sure that you can ever get consistent results if the input order 
is
> random.  The Collections.sort() implements a merge sort and the merge 
sort
> depends on a consistent result from the compare() method.  As 
implemented the
> compare() will return what you want when the object being compared 
against is
> the "Misc" object but return a string compare when it isn't.  Try this:

> @Override
> public int compareTo(Category c) {
> if(category.equals("Miscellaneous")){
> return 1;
> } elseif (c.category.equals("Miscellaneous")) {
> return -1;
> else{
> return category.compareTo(c.category);
> }
> }

> (side comment: If the list is a decent size it might make sense to 
compare
> against the Misc object rather than compare all strings but it's likely 
not
> worth the bother).

> The was I usually handle this is to .remove the offending object 
> from the list,
> sort, then .add it back on after the sort.  Keep the odd code local to 
the
> oddity.

This is closer, but still doesn't work correctly if two "Misc" categories 
are being compared, or one "Misc" category is compared to itself. 
Try: 

@Override
public int compareTo(Category c) {
        if(category.equals("Miscellaneous")) {
                if(category.equals(c.category) return 0; // correctly 
handle equality. 
                else return 1;
        } elseif (c.category.equals("Miscellaneous")) {
                return -1;
        } else {
                return category.compareTo(c.category);
        }
}

---------------------------------------------------
David S. Johnson
DeskNet Inc.




Re: This is just plain ... odd.

Posted by Lyallex <ly...@gmail.com>.
Don't shout at me for top posting
In this instance it's justified

Thanks for your continued work on this. I have to get some lines of code
down
as release date is fast approaching but I will try your code as soon as I
have time

Thanks for you continued work on this

Lyallex

On 9 November 2012 05:08, Christopher Schultz
<ch...@christopherschultz.net>wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Russ,
>
> On 11/8/12 6:05 PM, Russ Kepler wrote:
> > On Thursday, November 08, 2012 07:36:20 PM Lyallex wrote:
> >
> >> The only difference between the two executions is the fact that
> >> the test code executes in it's own instance of the JVM whereas
> >> the other execution runs in an instance shared with the
> >> container.
> >>
> >> I accept that the behaviour may be undefined even though it is
> >> consistently repeatable in both environments but surely given
> >> everything else being equal the results should be the same ... or
> >> maybe I'm just losing the plot.
> >
> > No, you're right but just missing some small difference in the
> > environments.
> >
> > I'd verify that you get the same input data in the same order in
> > both cases, and that you're starting with the same size container
> > [...]
>
> After writing a bench test that I couldn't get to fail, your comment
> here tripped a thought in my brain: the "container" size. So, I added
> an element to my list of Strings and boom: failure. It turns out that
> the collection size doesn't matter: I just hadn't been iterating
> enough, so I added a loop that will run until the initial sorted order
> doesn't match the re-sorted order (with shuffles in between).
>
> Lyallex, see the code below: it will fail after a few iterations to
> produce the same element ordering. Switch from BrokenSorter to
> WorkingSorter and you'll find that it runs forever.
>
> Are you *sure* that your database always returns the items in the same
> order? If you plan on sorting alphabetically later, why bother sorting
> by id when fetching? Unless you are really sorting by id when
> fetching, the data can come back in any order. It may *often* be in
> entry-sequenced order, but it is certainly not guaranteed to be.
>
> The code below shows that, without any funny business, the sort can
> work sometimes and not in others.
>
> Enjoy,
> - -chris
>
> import java.util.ArrayList;
> import java.util.Arrays;
> import java.util.Collections;
> import java.util.Comparator;
> import java.util.List;
>
> public class SortTest
> {
>     public static void main(String[] args)
>     {
>         String[] fruits = new String[] {
> "Apples",
> "Bananas",
> "Coconuts",
> "Dates",
> "Eggplants",
> "Figs",
> "Grapefruits",
> "Honeydews",
> "Ilamas",
> "Jambolans",
> "Kepels",
> "Lemons",
> "Miscellaneous",
> "Nectarines"
>         };
>
>         List<String> fruitList = Arrays.asList(fruits);
>
>         Comparator<String> sorter = new BrokenSorter();
>
>         System.out.println("Initial order: " + fruitList);
>
>         Collections.sort(fruitList, sorter);
>         System.out.println("Sort 1: " + fruitList);
>
>         List<String> saved = new ArrayList<String>(fruitList);
>
>         int i = 1;
>         do
>         {
>             Collections.shuffle(fruitList);
>             Collections.sort(fruitList, sorter);
>             System.out.println("Sort " + (++i) + ": " + fruitList);
>         }
>         while(fruitList.equals(saved));
>         System.out.println("Stopped after " + i + " iterations because
> the list did not sort the same way.");
>     }
>
>     static class BrokenSorter
>       implements Comparator<String>
>     {
>         @Override
>         public int compare(String a, String b)
>         {
>           if(a.equals("Miscellaneous"))
>               return 1;
>           return a.compareTo(b);
>         }
>     }
>     static class WorkingSorter
>       implements Comparator<String>
>     {
>         @Override
>         public int compare(String a, String b)
>         {
>           if(a.equals("Miscellaneous"))
>               return 1;
>
>           if(b.equals("Miscellaneous"))
>               return -1;
>
>           return a.compareTo(b);
>         }
>     }
> }
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG/MacGPG2 v2.0.17 (Darwin)
> Comment: GPGTools - http://gpgtools.org
> Comment: Using GnuPG with Mozilla - http://www.enigmail.net/
>
> iEYEARECAAYFAlCcj7cACgkQ9CaO5/Lv0PBpawCeORBT62XWcjyw+SruT6Bhkh50
> sDEAn1ZjSiPR70+DV/QVBFOjXKjH498o
> =F3QS
> -----END PGP SIGNATURE-----
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: users-unsubscribe@tomcat.apache.org
> For additional commands, e-mail: users-help@tomcat.apache.org
>
>

Re: This is just plain ... odd.

Posted by Christopher Schultz <ch...@christopherschultz.net>.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Russ,

On 11/8/12 6:05 PM, Russ Kepler wrote:
> On Thursday, November 08, 2012 07:36:20 PM Lyallex wrote:
> 
>> The only difference between the two executions is the fact that
>> the test code executes in it's own instance of the JVM whereas
>> the other execution runs in an instance shared with the
>> container.
>> 
>> I accept that the behaviour may be undefined even though it is
>> consistently repeatable in both environments but surely given
>> everything else being equal the results should be the same ... or
>> maybe I'm just losing the plot.
> 
> No, you're right but just missing some small difference in the
> environments.
> 
> I'd verify that you get the same input data in the same order in
> both cases, and that you're starting with the same size container
> [...]

After writing a bench test that I couldn't get to fail, your comment
here tripped a thought in my brain: the "container" size. So, I added
an element to my list of Strings and boom: failure. It turns out that
the collection size doesn't matter: I just hadn't been iterating
enough, so I added a loop that will run until the initial sorted order
doesn't match the re-sorted order (with shuffles in between).

Lyallex, see the code below: it will fail after a few iterations to
produce the same element ordering. Switch from BrokenSorter to
WorkingSorter and you'll find that it runs forever.

Are you *sure* that your database always returns the items in the same
order? If you plan on sorting alphabetically later, why bother sorting
by id when fetching? Unless you are really sorting by id when
fetching, the data can come back in any order. It may *often* be in
entry-sequenced order, but it is certainly not guaranteed to be.

The code below shows that, without any funny business, the sort can
work sometimes and not in others.

Enjoy,
- -chris

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class SortTest
{
    public static void main(String[] args)
    {
        String[] fruits = new String[] {
"Apples",
"Bananas",
"Coconuts",
"Dates",
"Eggplants",
"Figs",
"Grapefruits",
"Honeydews",
"Ilamas",
"Jambolans",
"Kepels",
"Lemons",
"Miscellaneous",
"Nectarines"
        };

        List<String> fruitList = Arrays.asList(fruits);

        Comparator<String> sorter = new BrokenSorter();

        System.out.println("Initial order: " + fruitList);

        Collections.sort(fruitList, sorter);
        System.out.println("Sort 1: " + fruitList);

        List<String> saved = new ArrayList<String>(fruitList);

        int i = 1;
        do
        {
            Collections.shuffle(fruitList);
            Collections.sort(fruitList, sorter);
            System.out.println("Sort " + (++i) + ": " + fruitList);
        }
        while(fruitList.equals(saved));
        System.out.println("Stopped after " + i + " iterations because
the list did not sort the same way.");
    }

    static class BrokenSorter
      implements Comparator<String>
    {
        @Override
        public int compare(String a, String b)
        {
          if(a.equals("Miscellaneous"))
              return 1;
          return a.compareTo(b);
        }
    }
    static class WorkingSorter
      implements Comparator<String>
    {
        @Override
        public int compare(String a, String b)
        {
          if(a.equals("Miscellaneous"))
              return 1;

          if(b.equals("Miscellaneous"))
              return -1;

          return a.compareTo(b);
        }
    }
}
-----BEGIN PGP SIGNATURE-----
Version: GnuPG/MacGPG2 v2.0.17 (Darwin)
Comment: GPGTools - http://gpgtools.org
Comment: Using GnuPG with Mozilla - http://www.enigmail.net/

iEYEARECAAYFAlCcj7cACgkQ9CaO5/Lv0PBpawCeORBT62XWcjyw+SruT6Bhkh50
sDEAn1ZjSiPR70+DV/QVBFOjXKjH498o
=F3QS
-----END PGP SIGNATURE-----

---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@tomcat.apache.org
For additional commands, e-mail: users-help@tomcat.apache.org


Re: This is just plain ... odd.

Posted by Russ Kepler <ru...@kepler-eng.com>.
On Thursday, November 08, 2012 07:36:20 PM Lyallex wrote:

> The only difference between the two executions is the fact that the test
> code executes in
> it's own instance of the JVM whereas the other execution runs in an
> instance shared with the container.
> 
> I accept that the behaviour may be undefined even though it is consistently
> repeatable in both environments
> but surely given everything else being equal the results should be the same
> ... or maybe I'm just losing the plot.

No, you're right but just missing some small difference in the environments.

I'd verify that you get the same input data in the same order in both cases, 
and that you're starting with the same size container and using the same sort, 
etc.  Something is different, if it isn't the data then it has to be in the 
code.  Last time I found something like this is was a replaced class caused by 
a classpath difference - maybe walk the debug and see exactly what is being 
executed in the sort?



---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@tomcat.apache.org
For additional commands, e-mail: users-help@tomcat.apache.org


Re: This is just plain ... odd.

Posted by Lyallex <ly...@gmail.com>.
> [snip]
>



> You got the same (wrongish) results since you gave the sort the same order
> in
> the list.  I can't recall how merge sort can freak out when given
> conflicting
> compares, I seem to recall that you might get an endless loop under some
> circumstances as it orders and reorders the same group of objects.
>

This is all very interesting, no really it is, but it doesn't really answer
the original question
which is that given the same initial data in the same initial order and
executing exactly the same code in the
same release of Java produces different results.

The only difference between the two executions is the fact that the test
code executes in
it's own instance of the JVM whereas the other execution runs in an
instance shared with the container.

I accept that the behaviour may be undefined even though it is consistently
repeatable in both environments
but surely given everything else being equal the results should be the same
... or maybe I'm just losing the plot.

Lyallex

Re: This is just plain ... odd.

Posted by Russ Kepler <ru...@kepler-eng.com>.
On Thursday, November 08, 2012 03:06:51 PM Lyallex wrote:
> > I'm not sure that you can ever get consistent results if the input order
> > is
> > random.
> 
> Well perhaps 'random' was a bit 'random' the select returns the data in the
> same order it was entered, ordered by id.
> Not necessarily the same as alpha as I'm sure you appreciate. the fact is
> that the data was always returned in the same order
> by the database, just not the order I wanted. This is why I was
> particularly confused.
> 
> Whatever, your code works, now I just gotta figure out why

Because you were only handling one end of the compare against the special 
object.  Since the special object could appear as the object to be compared 
against as well as the object performing the compare the merge sort was being 
given conflicting comparisons against the special object - always the greatest 
when the special was performing the compare and alphabetically(ish) when it 
was the object given to the compare method.

You got the same (wrongish) results since you gave the sort the same order in 
the list.  I can't recall how merge sort can freak out when given conflicting 
compares, I seem to recall that you might get an endless loop under some 
circumstances as it orders and reorders the same group of objects.

---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@tomcat.apache.org
For additional commands, e-mail: users-help@tomcat.apache.org


Re: This is just plain ... odd.

Posted by Lyallex <ly...@gmail.com>.
> I'm not sure that you can ever get consistent results if the input order is
> random.


Well perhaps 'random' was a bit 'random' the select returns the data in the
same order it was entered, ordered by id.
Not necessarily the same as alpha as I'm sure you appreciate. the fact is
that the data was always returned in the same order
by the database, just not the order I wanted. This is why I was
particularly confused.

Whatever, your code works, now I just gotta figure out why

Thanks

Lyallex

Re: This is just plain ... odd.

Posted by Russ Kepler <ru...@kepler-eng.com>.
On Thursday, November 08, 2012 01:35:55 PM Lyallex wrote:

> I have tried everything I can think of to reproduce this behaviour
> in a standalone Java program but the list is always returned
> as required. When I call the method from a servlet the list is always
> returned
> in it's natural order, I know collections.sort is being executed as
> the list is in alpha order, it's almost as if the comparator is being
> replaced in some way
> 
> I have no servlet filters or any other code 'in the way' between the facade
> and the initialization servlet.
> 
> Any ideas ?

I'm not sure that you can ever get consistent results if the input order is 
random.  The Collections.sort() implements a merge sort and the merge sort 
depends on a consistent result from the compare() method.  As implemented the 
compare() will return what you want when the object being compared against is 
the "Misc" object but return a string compare when it isn't.  Try this:

   @Override
   public int compareTo(Category c) {
      if(category.equals("Miscellaneous")){
      return 1;
   } elseif (c.category.equals("Miscellaneous")) {
	return -1;
   else{
      return category.compareTo(c.category);
   }
}

(side comment: If the list is a decent size it might make sense to compare 
against the Misc object rather than compare all strings but it's likely not 
worth the bother).

The was I usually handle this is to .remove the offending object from the list, 
sort, then .add it back on after the sort.  Keep the odd code local to the 
oddity.

---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@tomcat.apache.org
For additional commands, e-mail: users-help@tomcat.apache.org