Java Forum / General / August 2007
Cannot seem to lock HashMap
byoder@hotmail.com - 16 Aug 2007 00:52 GMT Basically the situation is that I have a HashMap (yes I know this is not synchronized and therefore must do it manually). The HashMap is used by two threads running concurrently, and one thread is adding values to the map while the other is iterating over the values. Now typically I would expect to get the ConcurrentModificationException - but I have tried to synchronize the object manually without any luck.
Perhaps I don't understand locking, but according to Java 1.5 API this should work, I wrote the following test class to demonstrait what I am trying to do:
import java.util.Collections; import java.util.Date; import java.util.HashMap; import java.util.Map;
public class TestIndex {
public static HashMap<Date, Date> values = new HashMap<Date, Date>();
public static void main(String[] args) { new Thread_1().start(); new Thread_2().start(); }
public static class Thread_1 extends Thread {
public Thread_1() { super("Thread_1"); this.setDaemon(false); }
public void run() { System.out.println("Thread_1 run..."); try { for (int i=0; i<1000000; i++) { TestIndex.values.put(new Date(),new Date()); }
} catch (Exception e) { e.printStackTrace(); } System.out.println("Thread_1 END"); } }
public static class Thread_2 extends Thread {
public Thread_2() { super("Thread_2"); this.setDaemon(false); }
public void run() { System.out.println("Thread_2 run..."); try { for (int i=0; i<1000000; i++) {
Map m = Collections.synchronizedMap(TestIndex.values); synchronized (m) { HashMap<Date, Date> newMap = new HashMap<Date, Date>(m); }
}
} catch (Exception e) { e.printStackTrace(); } System.out.println("Thread_2 END"); } }
}
SadRed - 16 Aug 2007 01:05 GMT On Aug 16, 8:52 am, byo...@hotmail.com wrote:
> Basically the situation is that I have a HashMap (yes I know this is > not synchronized and therefore must do it manually). The HashMap is [quoted text clipped - 69 lines] > > } Use this technique mentioned in the API documentation of the HashMap class: Map m = Collections.synchronizedMap(new HashMap(...));
Lew - 16 Aug 2007 01:36 GMT byo...@hotmail.com wrote:
>> Basically the situation is that I have a HashMap (yes I know this is >> not synchronized and therefore must do it manually). The HashMap is [quoted text clipped - 4 lines] >> >> Perhaps I don't understand locking, but according to Java 1.5 API this Rather than "locking" you should be thinking "synchronization".
>> should work, I wrote the following test class to demonstrait what I am >> trying to do: What are you trying to do? It's not clear from the code.
>> import java.util.Collections; >> import java.util.Date; [quoted text clipped - 23 lines] >> TestIndex.values.put(new Date(),new Date()); >> } Nothing is synchronized here.
>> } catch (Exception e) { >> e.printStackTrace(); [quoted text clipped - 19 lines] >> HashMap<Date, Date> newMap = new HashMap<Date, Date>(m); >> } OK, here you create a Map from your "values" Map a million times, doubly synchronized (?) and copied into another Map, which latter is then discarded.
>> } >> [quoted text clipped - 6 lines] >> >> } Your Thread_2 class creates a million copies of your values Map, possibly at various stages of its population with values, inside a synchronized block that synchronizes on a synchronized Map.
What are you really trying to do?
 Signature Lew
Owen Jacobson - 16 Aug 2007 01:43 GMT On Aug 15, 4:52 pm, byo...@hotmail.com wrote:
> Basically the situation is that I have a HashMap (yes I know this is > not synchronized and therefore must do it manually). The HashMap is [quoted text clipped - 69 lines] > > } Your Thread_1 thread is not participating in any synchronization whatsoever, which means your Thread_2 reader thread is subject to race conditions in a number of ways. As SadRed suggested, use the synchronizedMap wrapper provided by Collections; alternately, have Thread_1 also synchronize on the map while inserting entries:
public void run() { System.out.println("Thread_1 run..."); try { for (int i=0; i<1000000; i++) { synchronized (TestIndex.values) { TestIndex.values.put(new Date(),new Date()); } }
} catch (Exception e) { e.printStackTrace(); } System.out.println("Thread_1 END"); }
byoder@hotmail.com - 16 Aug 2007 16:50 GMT > On Aug 15, 4:52 pm, byo...@hotmail.com wrote: > [quoted text clipped - 95 lines] > > - Show quoted text - As to what I am trying to do: Basically I want to use the HashMap vs. Hashtable because it is faster, and because there is really only one situation that I have that needs to be synchronized. That situation is when I need to clone my HashMap. Unfortunatly when cloning my HashMap it is very likely that another thread is adding or removing values to the HashMap. So I need to somehow lock down the HashMap so that it cannot be modified while the clone method is called.
I tried to use the Collections.synchronizedMap() - with a synchronized block of code, thinking that this would "lock" the HashMap from allowing other threads to put values until after the synchronized block has completed. However it now occurs to me that I have to do this in both threads, otherwise it will not work. This leads me to think I should just use Hashtable since I cannot lock HashMap when I need to (all or nothing).
The above code is just an example to throw the concurrent exception, I know that it is just "throwing away" the HashMap it creates in thread 2. Again this is just for demo purposes.
Gordon Beaton - 16 Aug 2007 16:49 GMT > As to what I am trying to do: Basically I want to use the HashMap vs. > Hashtable because it is faster, and because there is really only one [quoted text clipped - 3 lines] > values to the HashMap. So I need to somehow lock down the HashMap so > that it cannot be modified while the clone method is called. Then you also must synchronize operations that add or remove values.
If you synchronize only while cloning, then only cloning becomes an exclusive operation (i.e. you can't clone the same table twice at the same time).
If you neglect to synchronize add or remove, then those operations are not affected by the synchronization on clone.
/gordon
--
byoder@hotmail.com - 16 Aug 2007 17:22 GMT Thanks for the reply - but I tried to synchronize on both HashMap put() and clone() operations, and that still does not work (I still get ConcurrentModificationException). Any ideas?
I was finally able to get something else working - although it is slow (see final example at end of posting). This just uses the wrapper class to do the locking, as the underlying Hashmap is not made public.
... CHANGES ONLY MADE TO TestContainer class ...
public static class TestContainer {
private HashMap<Date, Date> _values;
public TestContainer() { _values = new HashMap<Date, Date>(); }
public TestContainer(HashMap<Date, Date> v) { _values = v; }
private void put(Date key, Date value) {
Map<Date, Date> m = Collections.synchronizedMap(_values);
synchronized (m) { m.put(key, value); } }
public Date get(Date key) { return _values.get(key); }
public Object clone() {
TestContainer eStore = null;
Map<Date, Date> m = Collections.synchronizedMap(_values);
synchronized (m) { HashMap<Date, Date> cValues = new HashMap<Date, Date>(m); m.remove(ITFGlobalID.GID_FLAG); eStore = new TestContainer(cValues); } return eStore;
} }
Also here is my final code, that DOES work, but is not ideal (seems to run slow).
package com.sscims.casetracker;
import java.util.Collections; import java.util.Date; import java.util.HashMap; import java.util.Map;
import com.sscims.jeb.enterprise.ITFGlobalID;
public class TestIndex {
public static void main(String[] args) {
TestContainer c = new TestContainer(); new Thread_1(c).start(); new Thread_2(c).start(); }
public static class Thread_1 extends Thread {
TestContainer c;
public Thread_1(TestContainer c) { super("Thread_1"); this.setDaemon(false); this.c = c; }
public void run() { Date start = new Date(); System.out.println("Thread_1 run..."); try { for (int i=0; i<1000000; i++) { Date key = new Date(); c.put(key,new Date()); c.get(key); }
} catch (Exception e) { e.printStackTrace(); } Date end = new Date(); long diff = end.getTime() - start.getTime(); System.out.println("Thread_1 END: " + diff + " total time"); } }
public static class Thread_2 extends Thread {
TestContainer c;
public Thread_2(TestContainer c) { super("Thread_2"); this.setDaemon(false); this.c = c; }
public void run() { Date start = new Date(); System.out.println("Thread_2 run..."); try { for (int i=0; i<1000000; i++) { c.clone(); }
} catch (Exception e) { e.printStackTrace(); } Date end = new Date(); long diff = end.getTime() - start.getTime(); System.out.println("Thread_2 END: " + diff + " total time"); } }
public static class TestContainer {
private HashMap<Date, Date> _values;
public TestContainer() { _values = new HashMap<Date, Date>(); }
public TestContainer(HashMap<Date, Date> v) { _values = v; }
private synchronized void put(Date key, Date value) { _values.put(key, value); }
public Date get(Date key) { return _values.get(key); }
public synchronized Object clone() { synchronized (this) { HashMap<Date, Date> cValues = new HashMap<Date, Date>(_values); cValues.remove(ITFGlobalID.GID_FLAG); return new TestContainer(cValues); } } } }
byoder@hotmail.com - 16 Aug 2007 17:40 GMT I found the following from Sun:
"Note that constructors cannot be synchronized - using the synchronized keyword with a constructor is a syntax error. Synchronizing constructors doesn't make sense, because only the thread that creates an object should have access to it while it is being constructed."
[http://java.sun.com/docs/books/tutorial/essential/concurrency/ syncmeth.html]
So it would seem that I should use clone() method, but this is not available from the Map that is returned from the Collections.synchronizedMap method. So it seems that I cannot do what I would like because of this. I think I either have to use Hashtable, or use a wrapper class (above example) to do the locking.
Thanks everybody...
Lew - 16 Aug 2007 23:32 GMT > I found the following from Sun: > [quoted text clipped - 12 lines] > I would like because of this. I think I either have to use Hashtable, > or use a wrapper class (above example) to do the locking. Constructors have nothing to do with your issue.
Your problem stemmed from not synchronizing your puts on the Map.
You might also consider just declaring the Map instance variable as a synchronized Map in the first place, thus avoiding the Hashtable gotchas. (Speed isn't one of them.)
> public static class TestContainer { A "static" class? Was this a nested class? If so, you should post the outer class, too, to make an SSCCE. If not, then you should post code that will compile.
And stop embedding TAB characters in Usenet posts.
private final Map<Date, Date> values; // use the interface, not the concrete class
> public TestContainer() { this( new HashMap<Date, Date>() );
> } > > public TestContainer( Map<Date, Date> v) { //again, use the interface if ( v == null ) { throw new IllegalArgumentException( "Map must not be null." ); }
> values = Collections.synchronizedMap( v ); > } [quoted text clipped - 5 lines] > public Date get(Date key) { > return values.get(key); See? /Now/ this is synchronized. It wasn't before.
> } > > public Object clone() { synchronized ( values ) { // prevent concurrent mod during clone() Map<Date, Date> cValues = new HashMap<Date, Date>( values ); values.remove(ITFGlobalID.GID_FLAG); return new TestContainer( cValues );
> } > } > } Another approach is to copy the Map in the constructor, thus avoiding most of the issue.
 Signature Lew
Lew - 16 Aug 2007 23:37 GMT > I found the following from Sun: > [quoted text clipped - 12 lines] > I would like because of this. I think I either have to use Hashtable, > or use a wrapper class (above example) to do the locking. Constructors have nothing to do with your issue.
Your problem stemmed from not synchronizing your puts or gets on the Map.
You might also consider just declaring the Map instance variable as a synchronized Map in the first place, thus avoiding the Hashtable gotchas. (Speed isn't one of them.)
> public static class TestContainer { /* A "static" class? Was this a nested class? If so, you should post the outer class, too, to make an SSCCE. If not, then you should post code that will compile.
And stop embedding TAB characters in Usenet posts. */ private final Map<Date, Date> values; // use the interface, not the concrete class
> public TestContainer() { this( new HashMap<Date, Date>() );
> } > > public TestContainer( Map<Date, Date> v) { //again, use the interface if ( v == null ) { throw new IllegalArgumentException( "Map must not be null." ); }
> values = Collections.synchronizedMap( v ); > } > > private void put(Date key, Date value) {
> values.put( key, value ); // See? /Now/ this is synchronized. It wasn't before.
> } > > public Date get(Date key) {
> return values.get(key); // See? /Now/ this is synchronized. It wasn't before.
> } > > public Object clone() { // prevent concurrent mod during clone() synchronized ( values ) { Map<Date, Date> cValues = new HashMap<Date, Date>( values ); values.remove(ITFGlobalID.GID_FLAG); return new TestContainer( cValues );
> } > } > } Another approach is to copy the Map in the constructor, thus avoiding most of the issue.
 Signature Lew
byoder@hotmail.com - 20 Aug 2007 21:17 GMT Lew -
Sorry for the TABS (I copied code from Eclipse). I do agree that your code may work, but I would be paying penalty of having to synchronize (lock) for every call that uses "values".
But I found solution that allows me to ONLY synchronize methods that either depend on the map NOT getting modified, and methods that modify the map. To do this I must synchronize all methods that can modify the map, but all methods that don't need to synchronize the map (such as get() don't depend on any locking) are not synchronized so there is no locking and thus are faster.
Any methods that depend on the map data TO NOT CHANGE I explicitly lock the container class. This is the best approach because I don't have to pay penalty for locking (synchronizing) all of my methods - which is the solution I was looking for as speed is very important to me in this code.
See example (two classes):
public class TestIndex {
public static void main(String[] args) {
TestContainer c = new TestContainer(); new Thread_1(c).start(); new Thread_2(c).start(); }
public static class Thread_1 extends Thread {
TestContainer c;
public Thread_1(TestContainer c) { super("Thread_1"); this.setDaemon(false); this.c = c; }
public void run() { Date start = new Date(); System.out.println("Thread_1 run..."); try { for (int i=0; i<1000000; i++) { Date key = new Date(); c.put(key,new Date()); c.get(key); }
} catch (Exception e) { e.printStackTrace(); } Date end = new Date(); long diff = end.getTime() - start.getTime(); System.out.println("Thread_1 END: " + diff + " total time"); } }
public static class Thread_2 extends Thread {
TestContainer c;
public Thread_2(TestContainer c) { super("Thread_2"); this.setDaemon(false); this.c = c; }
public void run() { Date start = new Date(); System.out.println("Thread_2 run..."); try { for (int i=0; i<1000000; i++) { c.clone(); }
} catch (Exception e) { e.printStackTrace(); } Date end = new Date(); long diff = end.getTime() - start.getTime(); System.out.println("Thread_2 END: " + diff + " total time"); } } }
public class TestContainer {
private HashMap<Date, Date> _values;
public TestContainer() { _values = new HashMap<Date, Date>(); }
public TestContainer(HashMap<Date, Date> v) { _values = v; }
public void put(Date key, Date value) { _values.put(key, value); }
public Date get(Date key) { return _values.get(key); }
public Object clone() {
HashMap<Date, Date> cValues = new HashMap<Date, Date>(_values.size());
synchronized (this) { cValues.putAll(_values); } return new TestContainer(cValues); } }
Lew - 20 Aug 2007 23:03 GMT > Lew - > > Sorry for the TABS (I copied code from Eclipse). I do agree that your > code may work, but I would be paying penalty of having to synchronize > (lock) for every call that uses "values". It is necessary to synchronize every access to a shared resource if you want to avoid memory model anomalies.
> But I found solution that allows me to ONLY synchronize methods that > either depend on the map NOT getting modified, and methods that modify > the map. To do this I must synchronize all methods that can modify > the map, but all methods that don't need to synchronize the map (such > as get() don't depend on any locking) are not synchronized so there is > no locking and thus are faster. This means that you risk having the get() return different values than were put().
> Any methods that depend on the map data TO NOT CHANGE I explicitly > lock the container class. This is the best approach because I don't > have to pay penalty for locking (synchronizing) all of my methods - The "penalty" is not so large, and certainly smaller than getting the wrong results.
> which is the solution I was looking for as speed is very important to > me in this code. But correct results are not?
> See example (two classes): > [quoted text clipped - 24 lines] > Date key = new Date(); > c.put(key,new Date());
> c.get(key); > } [quoted text clipped - 39 lines] > > private HashMap<Date, Date> _values; Apparently you overlooked the suggestion to declare this as a Map rather than a HashMap.
> public TestContainer() { > _values = new HashMap<Date, Date>(); [quoted text clipped - 6 lines] > public void put(Date key, Date value) { > _values.put(key, value); This unsynchronized access will cause trouble.
> } > > public Date get(Date key) { > return _values.get(key); This unsynchronized access will cause trouble.
> } > > public Object clone() { > > HashMap<Date, Date> cValues = new HashMap<Date, > Date>(_values.size()); This unsynchronized access will cause trouble.
Declare the variable as the interface type, instantiate as the concrete type.
> synchronized (this) { > cValues.putAll(_values); Synchronizing on only one access to a protected resource but leaving the rest unsynchronized causes bugs.
> } > return new TestContainer(cValues); > } > } Your code is subject to a host of ills because you aren't synchronizing your access to a shared resource.
 Signature Lew
byoder@hotmail.com - 21 Aug 2007 01:54 GMT You are correct, I posted the wrong version of my code. The "public void put()..." should have read "public synchronized void put()..." - so you are correct on this point.
>> But correct results are not? No, not really. I DO NOT care if the value returned from get() is "up- to-date" or not, think of it like "dirty read". My requirements are very simple...
a) I must be able to put NULL values (not keys) in my map. Therefore I cannot use ConcurrentHashMap, Hashtable. b) I don't want to synchronize ALL methods, such as get() methods, since I don't care if the data has changed - I allow dirty read (old data). c) I must never throw ConcurrentModificationException. Therefore I must be sure that I synchronize methods that either (a) modify the data (the put method) OR (b) methods that rely on the data not getting modified during execution (the clone method).
HashMap states the following:
"If multiple threads access this map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with a key that an instance already contains is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the map".
"synchronizing on some object" is done via my TestContainer class, so I beleive I have accomplished this. And Sun also states that "If no such object exists, the map should be 'wrapped' using the Collections.synchronizedMap" - but this is an alternative, NOT in addition to. See http://java.sun.com/j2se/1.5.0/docs/api/java/util/HashMap.html
So that said I feel I am OK to allow the get() method to run unsynchronized, but in short I agree the clone and put methods (in the TestContainer class) MUST BOTH be synchronized which they were not in my prior post.
Thanks for the conversation - this has been real
Patricia Shanahan - 21 Aug 2007 02:14 GMT > You are correct, I posted the wrong version of my code. The "public > void put()..." should have read "public synchronized void put()..." - [quoted text clipped - 5 lines] > to-date" or not, think of it like "dirty read". My requirements are > very simple... You seem to be assuming atomic behavior, so that the get result is either the old or the new value. There is nothing in the API documentation that promises atomic get.
As far as I can tell, the actual get implementation has real vulnerabilities, even in a simple single processor situation, without getting into the complexities of memory order.
Consider the following two lines from the get implementation:
int i = indexFor(hash, table.length); Entry<K,V> e = table[i];
Suppose there is an interrupt and context switch between the two lines. Some other thread does a put that causes a rehash with a larger table size. The hash may no longer belong in bucket i. If get searches the wrong bucket it will return null regardless of whether the key is actually present or not.
This could happen with everything else synchronized, as long as get itself is not synchronized.
Patricia
Lew - 21 Aug 2007 05:58 GMT >> You are correct, I posted the wrong version of my code. The "public >> void put()..." should have read "public synchronized void put()..." - [quoted text clipped - 27 lines] > This could happen with everything else synchronized, as long as get > itself is not synchronized. What we are trying to point out is that you can't only synchronize some of the methods that access the Map and not others. It's all or nothing. That's the way it is. You cannot safely synchronize only some of the methods that access the Map.
 Signature Lew
byoder@hotmail.com - 21 Aug 2007 06:30 GMT This is a good point, but I am not sure if you are correct (this is getting a bit out of my league). It appears that the HashMap.Entry DOES depends on the table.length - so it is sensitive to changes in size.
But I cannot say for sure if this will cause the behavior or problems you mention above (return NULL becuase of unsynchronized get() method). One thing that leads me to think you ARE correct is the implementation of Hashtable HAS a synchronized get() method. But it seems strange to me that HashMap would have such a BIG vunerability in it - but perhaps that is what you get when using unsynchronized HashMap vs. Hashtable.
Any Java experts care to expand on this?
I think that tomorrow I will take the HashMap source code and run some tests to prove or disprove this theory, since I cannot tell by looking at it. But if true, then I will need to also synchronize the get() method in my wrapper class.
Below methods are from HashMap.java (1.5.0_12):
public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; }
static int indexFor(int h, int length) { return h & (length-1); }
public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } }
modCount++; addEntry(hash, key, value, i); return null; }
void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); }
Patricia Shanahan - 21 Aug 2007 15:08 GMT ...
> But I cannot say for sure if this will cause the behavior or problems > you mention above (return NULL becuase of unsynchronized get() [quoted text clipped - 3 lines] > it - but perhaps that is what you get when using unsynchronized > HashMap vs. Hashtable. I am not suggesting a vulnerability in the sense of a failure of HashMap to conform to its contract. The scenario requires a structural change to the map while get is running. The API documentation says "If multiple threads access this map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally.". The vulnerability lies in trying to use HashMap in a way that is contrary to its contract.
The scenario is a simple single processor case. How well do you understand the Java memory model? See http://java.sun.com/docs/books/jls/third_edition/html/memory.html#17.4
> I think that tomorrow I will take the HashMap source code and run some > tests to prove or disprove this theory, since I cannot tell by looking > at it. But if true, then I will need to also synchronize the get() > method in my wrapper class. Synchronization bugs may be hard to reproduce, and remember that you don't just have to deal with the one scenario I suggested. In order to not synchronize get you would need to look at its interaction with every method in HashMap.
An easier approach might be to first do a performance test simply synchronizing get. It may run fast enough. For the default load level, the average chain length it needs to search is 0.75 entries. If get is too slow to synchronize, I would suspect a bad hashCode function in the key class, and try to fix that.
> Below methods are from HashMap.java (1.5.0_12): > [quoted text clipped - 16 lines] > return h & (length-1); > } I looked at 1.5.0_3. The same point applies to the later code - consider a resize happening anywhere between indexFor committing to its result and the end of the search.
This brings out an important point. If you are going to depend for correctness of your program on assumptions about how API methods are implemented, you cannot just review one implementation. You need to review EVERY version on which you intend to support your program.
Patricia
sentientholon - 21 Aug 2007 15:37 GMT On Aug 21, 12:30 am, byo...@hotmail.com wrote:
> This is a good point, but I am not sure if you are correct (this is > getting a bit out of my league). It appears that the HashMap.Entry [quoted text clipped - 8 lines] > it - but perhaps that is what you get when using unsynchronized > HashMap vs. Hashtable. The unsynchronized behavior of HashMap is simply there so you can use it without synchronization when you don't need to. The wrapper provided by Collections.synchronizedMap(...) is sufficient for safe concurrent use, as long as everybody who interacts with the underlying Map does so through the same wrapper (duh).
As Patricia has noted - yes, accesses have to be synchronized as well as mutations, because a get is completely non-atomic in this situation. I believe there are some utility libraries out there that provide some "dirty read" types of functionality, by doing various kinds of copy-on-write tricks, but the Collections API doesn't promise anything of the sort. Maybe something like this is what you are looking for?
http://commons.apache.org/collections/api-release/org/apache/commons/collections /FastHashMap.html
Fred
Roedy Green - 17 Aug 2007 01:41 GMT >Perhaps I don't understand locking, The key fact you are missing is that EVERYONE using a contentious resource must lock it. You lock it only in your second thread. see http://mindprod.com/jgloss/thread.html
 Signature Roedy Green Canadian Mind Products The Java Glossary http://mindprod.com
Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
|
|