프로젝트를 하다보면 다중 선택 구조를 구현해야 할 때가 있다.
예를 들어, 일자리 중개 서비스를 만들 때 근무 가능 요일을 월화수목금토일 중에서 자유롭게 선택하는 구조가 될 수 있다.
이때는 하나만 선택 가능한 것이 아니라, 여러 개를 중복으로 선택할 수 있기 때문에, 사용자의 선택값을 어떻게 데이터베이스에 저장할 지 고민이 필요했다.
JPA로 테이블을 구현하면서 이 데이터를 어떻게 저장할 지 찾아보다가 EnumSet 이라는 컬렉션을 알게 되었다.
말그대로 Enum 타입 데이터를 갖는 Set 으로 다른 Set에 비해 더 빠르게 읽고 쓰기를 할 수 있다고 한다.
A specialized Set implementation for use with enum types. All of the elements in an enum set must come from a single enum type that is specified, explicitly or implicitly, when the set is created. Enum sets are represented internally as bit vectors. This representation is extremely compact and efficient. The space and time performance of this class should be good enough to allow its use as a high-quality, typesafe alternative to traditional int-based "bit flags." Even bulk operations (such as containsAll and retainAll) should run very quickly if their argument is also an enum set.
Set 인터페이스에 대한 구현 중 하나로, enum 타입을 사용하기 위한 Set 이다.
EnumSet 은 내부적으로 bit vector 들로 데이터를 표현하고 있어 효율적이고 압축적이다.
따라서 기존의 int-based bit flags 를 대체해서 사용하기에 좋다.
게다가 대량의 데이터를 조회하는 bulk operation 에 대해서도 빠르게 수행할 수 있다.
클래스 구조와 동작 뜯어보기
EnumSet 의 클래스 다이어그램을 보면 위와 같다.
기본적으로 AbstractSet 을 상속하고, AbstractSet 이 Set 에 대한 구현인 동시에 AbstractCollection 을 상속하고 있다.
여기에서 EnumSet 이 일반 클래스가 아니라 abstract class 라는 것을 발견했다.
그렇다면 interface와 abstract class 사이의 차이점은 무엇일까?
집에 있는 명품 Java 프로그래밍 책의 설명에 따르면 다음과 같다.
abstract class는 class의 일종으로, 멤버 변수를 가질 수 있으며, 일부 메서드는 직접 구현하고, 일부 메서드를 추상 메서드로 남겨두어 자식 클래스에서 구현하도록 할 수 있다. 클래스이기 때문에 다중상속할 수 없다.
interface는 class가 아니므로 멤버 변수를 가질 수 없으며, 모든 메서드가 추상메서드이고 메서드에 대한 구현은 존재할 수 없다.
다중상속이 가능하다.
두 클래스 모두 polymorphism (one interface, multiple implementations) 를 지원하기 위한 방법이라는 공통점이 있다.
public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) {
Enum<?>[] universe = getUniverse(elementType);
if (universe == null)
throw new ClassCastException(elementType + " not an enum");
if (universe.length <= 64)
return new RegularEnumSet<>(elementType, universe);
else
return new JumboEnumSet<>(elementType, universe);
}
그래서 EnumSet 클래스를 보면 위와 같이 일부 메서드의 동작은 구현이 되어있다.
noneOf() 메서드는 비어있는 EnumSet 객체를 생성하는 코드로, enum 을 구성하는 데이터 종류가 64개 이하면 RegularEnumSet 이라는 구현체를, 64개보다 많으면 JumboEnumSet 이라는 구현체를 사용하여 객체를 생성한다.
(EnumSet 클래스는 추상클래스 이므로 구 자체로 객체를 생성할 수 없다.)
enum 을 구성하는 데이터의 종류가 64개를 넘어가는 일은 흔하지 않으므로, RegularEnumSet의 구현을 위주로 살펴보려고 한다.
구현 클래스에서는 실제로 Set에 데이터를 추가하고 삭제하는 로직을 구현하고 있다.
/**
* The class of all the elements of this set.
*/
final transient Class<E> elementType;
/**
* All of the values comprising E. (Cached for performance.)
*/
final transient Enum<?>[] universe;
위 코드에서 잠깐 본 것처럼 EnumSet 내부에는 universe 라는 필드에 모든 enum 의 데이터를 캐싱하는 공간이 있다.
이때 transient 라는 키워드로 멤버 변수가 선언되었다.
처음 들어보는 키워드라 한번 찾아보았다.
이 키워드는 Serializable 과 관련되어 있는 키워드로, 클래스의 데이터를 직렬화 할 때, 보안이나 불필요 데이터를 제거하고자 필드의 실제 값을 null 로 직렬화하고자 할 때 사용한다.
예를 들어 Member 클래스에 name, age 필드가 있을 때, name 에 대해 transient 키워드가 있다면 Member 객체를 직렬화 할 때 {name: null, age: 20} 과 같이 name 필드의 실제 값을 null 로 보여준다.
데이터 추가, 삭제
다시 EnumSet 의 구현으로 돌아와서, RegularEnumSet이 데이터를 어떻게 추가하고 삭제하는지 살펴보자.
/**
* Adds the specified element to this set if it is not already present.
*
* @param e element to be added to this set
* @return {@code true} if the set changed as a result of the call
*
* @throws NullPointerException if {@code e} is null
*/
public boolean add(E e) {
typeCheck(e);
long oldElements = elements;
elements |= (1L << ((Enum<?>)e).ordinal());
return elements != oldElements;
}
먼저 추가하려는 데이터의 타입을 체크한다.
매개변수로 들어온 타입이 EnumSet 을 생성할 때 명시했던 EnumType 또는 그 슈퍼 클래스의 타입과 다르면 ClassCastException을 발생시킨다.
만약 매개변수로 들어온 타입이 null 이면 NPE를 발생시킨다.
/**
* Bit vector representation of this set. The 2^k bit indicates the
* presence of universe[k] in this set.
*/
private long elements = 0L;
EnumSet 은 최대 64종류의 데이터를 저장하기 위해 long 타입으로 선언된 elements 라는 bit vector 를 사용한다.
(long 타입이 64bit 이기 때문에 64종류를 넘어가는 데이터는 JumboEnumSet 을 사용하여 구현했던 것이다.)
데이터를 추가할 땐 기존 bit 정보를 읽어온 뒤 bit or 연산으로 현재 enum value 의 순서에 맞는 비트를 활성화한다.
예를 들어 4가지 데이터가 있다고 할 때, 처음에는 0000 이었다가, 2번째 enum 데이터를 set에 추가하면 0010 이 된다.
void complement() {
if (universe.length != 0) {
elements = ~elements;
elements &= -1L >>> -universe.length; // Mask unused bits
}
}
이 메서드는 집합의 여집합을 구하는 메서드이다.
~ 연산자를 사용하여 모든 비트를 반전시킨 뒤, universe 의 크기를 고려하여 사용하지 않는 비트를 마스킹한다.
구체적인 예시를 보자면 4가지 데이터를 가진 enum 에 대한 enum set 에서 1번째, 3번째 데이터가 들어있다고 해보자.
그러면 논리적으로는 0101 과 같이 비트마스크로 표현하고 있을 것이다.
하지만 실제 element 의 크기는 64bit 이므로 0000000000....0101 과 같이 표현되어있다.
이 상태에서 비트를 반전시키면 1111111.....1010 이 되어 우리가 생각한 것과 다른 값이 나온다.
따라서 오른쪽 4개의 비트만 사용하기 위해서 -1 을 오른쪽으로 -4 만큼 이동한다.
이때 오른쪽으로 -3 만큼 이동한다는 것은, long 타입 기준 64 - 4 = 60 번 이동한다는 것과 같다.
-1 은 이진수로 11111111....111 이므로 이를 60번 오른쪽으로 밀고, 밀어낸 자리를 0으로 채우면 00000....001111 이 된다.
이 값을 기존의 반전시킨 element 와 bit and 연산한다는 것은 사실상 최하위 4개 비트만 유효하게 놔두고, 나머지는 모두 0으로 지우겠다는 것과 같다.
결론적으로 비트를 반전시킨 뒤, 그 결과에서 실제 universe 개수만큼의 하위 비트만 놔두고 나머지를 0으로 초기화한다.
void addAll() {
if (universe.length != 0)
elements = -1L >>> -universe.length;
}
같은 원리로 addAll() 은 모든 종류의 enum 값을 set에 넣겠다는 뜻이므로, 00000...001111 을 그대로 element로 저장하여 유효한 모든 필드를 1로 세팅하게 된다.
/**
* Removes the specified element from this set if it is present.
*
* @param e element to be removed from this set, if present
* @return {@code true} if the set contained the specified element
*/
public boolean remove(Object e) {
if (e == null)
return false;
Class<?> eClass = e.getClass();
if (eClass != elementType && eClass.getSuperclass() != elementType)
return false;
long oldElements = elements;
elements &= ~(1L << ((Enum<?>)e).ordinal());
return elements != oldElements;
}
데이터를 삭제할 때는 해당 데이터가 null 이 아니고, EnumSet에서 다루는 클래스에 속하는 지 확인한다.
다룰 수 있는 enum 타입이라면 해당 enum 데이터 순번을 제외하고 활성화된 비트로 and 연산을 한다.
예를 들어 4개 데이터로 구성된 enum 중에서 3번째 데이터를 삭제하고자 한다면
0100 으로 세번째 데이터를 나타내는 비트를 만들고, 이를 뒤집어서 1011 로 만든 뒤 기존 비트마스크에 and 연산하면 3번째 데이터는 무조건 0이 되고, 나머지 값은 기존 값을 그대로 유지한다.
remove 메서드의 응답값은 remove 연산 이후 set 에 변화가 생겼는지 여부를 응답한다.
데이터 조회
이쯤되면 데이터 조회는 어떻게 할 지 대충 감이 온다.
/**
* Returns {@code true} if this set contains the specified element.
*
* @param e element to be checked for containment in this collection
* @return {@code true} if this set contains the specified element
*/
public boolean contains(Object e) {
if (e == null)
return false;
Class<?> eClass = e.getClass();
if (eClass != elementType && eClass.getSuperclass() != elementType)
return false;
return (elements & (1L << ((Enum<?>)e).ordinal())) != 0;
}
Set 연산의 핵심은 특정 데이터가 포함되어있는지 검사하는 것이다.
이는 기존 element 비트마스크에서 찾고자 하는 데이터의 위치에 해당하는 비트가 활성화되어 있는지 확인하는 것과 같다.
찾고자 하는 데이터가 세번째 데이터라면 0100 과 element를 & 연산하여 그 결과가 0이 아닌지를 확인하면 된다.
여러 데이터를 조회하거나, 추가하는 bulk 연산은 어떻게 처리할까?
/**
* Returns {@code true} if this set contains all of the elements
* in the specified collection.
*
* @param c collection to be checked for containment in this set
* @return {@code true} if this set contains all of the elements
* in the specified collection
* @throws NullPointerException if the specified collection is null
*/
public boolean containsAll(Collection<?> c) {
if (!(c instanceof RegularEnumSet<?> es))
return super.containsAll(c);
if (es.elementType != elementType)
return es.isEmpty();
return (es.elements & ~elements) == 0;
}
주어진 컬렉션에 해당하는 모든 데이터를 다 포함하고 있는지 검사한다.
만약 주어진 컬렉션이 RegularEnumSet 이 아니라면 부모 클래스 (EnumSet) 에 정의된 containsAll() 을 호출한다.
만약 같은 RegularEnumSet 에 대한 비교라면 대상 enum set 과 나를 반전시킨 비트마스크의 & 연산이 0인지 보면 된다.
예를 들어, 비교 대상 enum 은 1, 3번째 데이터를 가진 0101 이고, 나는 2, 4번째 데이터를 가진 1010 이라고 해보자.
나를 반전시키면 0101 이고, 이 결과를 & 연산하면 0101 이므로 0이 아니다. 따라서 모든 데이터를 갖고 있지는 않다.
비교 대상 enum은 1, 3 번째 데이터를 가진 0101 이고, 나는 1, 4 번째 데이터를 가진 1001 이라면,
나를 반전했을 때 0110 이고, 이를 0101 과 & 연산하면 0100 이므로 0이 아니다.
마지막으로 같은 비교 대상에 대해 나는 1, 2, 3 번째 데이터를 가진 0111 이라고 하면,
나를 반전했을 대 1000 이고, 이를 0101 과 & 연산하면 0000 이므로 0이다.
따라서 비교대상이 가진 모든 데이터를 나도 갖고 있음을 알 수 있다.
이렇게 비트연산을 통해 대량의 벌크연산을 매우 빠르고 효율적으로 처리할 수 있다.
단 비교 대상이 RegularEnumSet 이 아니라면 비교 대상 컬렉션을 순회해서 체크하게 되므로, O(N) 의 시간복잡도가 소요된다.
/**
* Adds all of the elements in the specified collection to this set.
*
* @param c collection whose elements are to be added to this set
* @return {@code true} if this set changed as a result of the call
* @throws NullPointerException if the specified collection or any
* of its elements are null
*/
public boolean addAll(Collection<? extends E> c) {
if (!(c instanceof RegularEnumSet<?> es))
return super.addAll(c);
if (es.elementType != elementType) {
if (es.isEmpty())
return false;
else
throw new ClassCastException(
es.elementType + " != " + elementType);
}
long oldElements = elements;
elements |= es.elements;
return elements != oldElements;
}
여러 데이터를 한번에 추가하는 것 역시 빠르고 효율적이다.
만약 RegularEnumSet 이 아닌 데이터에서 추가한다면 컬렉션을 순회하면서 추가하므로 O(N) 이 소요된다.
RegularEnumSet 이더라도, 그 내부 enum 타입이 다르면 에러가 발생하고, 같으면 각자가 가진 element 를 or 연산만 하면 끝이다.
따라서 상수시간에 빠르게 데이터를 추가할 수 있다.
/**
* Removes from this set all of its elements that are contained in
* the specified collection.
*
* @param c elements to be removed from this set
* @return {@code true} if this set changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean removeAll(Collection<?> c) {
if (!(c instanceof RegularEnumSet<?> es))
return super.removeAll(c);
if (es.elementType != elementType)
return false;
long oldElements = elements;
elements &= ~es.elements;
return elements != oldElements;
}
데이터를 지우는 것 역시, 기준 데이터를 반전해서 & 연산하면 끝이다.
/**
* Retains only the elements in this set that are contained in the
* specified collection.
*
* @param c elements to be retained in this set
* @return {@code true} if this set changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean retainAll(Collection<?> c) {
if (!(c instanceof RegularEnumSet<?> es))
return super.retainAll(c);
if (es.elementType != elementType) {
boolean changed = (elements != 0);
elements = 0;
return changed;
}
long oldElements = elements;
elements &= es.elements;
return elements != oldElements;
}
마지막으로, 입력으로 주어진 collection 에 있는 데이터만 남기고 모두 지우는 retainAll() 연산 역시 비트 and 연산으로 한번에 깔끔하게 된다.
Implementation note: All basic operations execute in constant time. They are likely (though not guaranteed) to be much faster than their HashSet counterparts. Even bulk operations execute in constant time if their argument is also an enum set.
이제 공식문서에 적혀있는 구현에 대한 참고 설명이 이해가 된다.
집합 연산에 대한 argument 가 같은 enum set 이면 bulk 연산조차 상수시간에 수행되며, 일반적으로 hash set 의 각 연산보다 더 빠르게 수행된다.
Thread-Safe
Like most collection implementations, EnumSet is not synchronized. If multiple threads access an enum set concurrently, and at least one of the threads modifies the set, it should be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the enum set. If no such object exists, the set should be "wrapped" using the Collections.synchronizedSet method. This is best done at creation time, to prevent accidental unsynchronized access:
Set<MyEnum> s = Collections.synchronizedSet(EnumSet.noneOf(MyEnum.class));
공식문서의 설명을 보면 이런 설명도 있다.
대부분의 컬렉션 구현과 마찬가지로, EnumSet 은 동기화되지 않는다고 한다.
만약 여러 스레드가 하나의 EnumSet에 동시에 접근하고, 이 중 적어도 1개의 스레드에서 EnumSet에 수정을 가하면, 나머지 스레드에서는 그 변경되지 이전의 값을 읽는 팬텀 리드 문제가 발생할 수 있다.
즉, EnumSet은 Thread-Safe 하지 않다.
따라서 이 문제를 예방하고 싶다면 위에 나와 있는 예시처럼 Collections.synchronizedSet() 으로 감싸 생성해서, EnumSet 외부에서 동기화를 해주도록 해야 한다.
/**
* Returns a synchronized (thread-safe) collection backed by the specified
* collection. In order to guarantee serial access, it is critical that
* <strong>all</strong> access to the backing collection is accomplished
* through the returned collection.<p>
*
* It is imperative that the user manually synchronize on the returned
* collection when traversing it via {@link Iterator}, {@link Spliterator}
* or {@link Stream}:
* <pre>
* Collection c = Collections.synchronizedCollection(myCollection);
* ...
* synchronized (c) {
* Iterator i = c.iterator(); // Must be in the synchronized block
* while (i.hasNext())
* foo(i.next());
* }
* </pre>
* Failure to follow this advice may result in non-deterministic behavior.
*
* <p>The returned collection does <i>not</i> pass the {@code hashCode}
* and {@code equals} operations through to the backing collection, but
* relies on {@code Object}'s equals and hashCode methods. This is
* necessary to preserve the contracts of these operations in the case
* that the backing collection is a set or a list.<p>
*
* The returned collection will be serializable if the specified collection
* is serializable.
*
* @param <T> the class of the objects in the collection
* @param c the collection to be "wrapped" in a synchronized collection.
* @return a synchronized view of the specified collection.
*/
public static <T> Collection<T> synchronizedCollection(Collection<T> c) {
return new SynchronizedCollection<>(c);
}
기존의 컬렉션을 synchronizedCollection 으로 감싸서, 이 컬렉션을 통과한 뒤에야 기존 컬렉션에 접근할 수 있도록 앞에 프록시 객체를 두는 느낌이다.
그리고 Iterator, Stream, Splitorator 등을 사용하여 컬렉션을 순회할 때는 synchronized 라는 자바의 키워드를 선언하고, 이 블록 내에서 순회할 것을 권장하고 있다.
이렇게 안하면 의도치 않게 동작할 수 있다고 경고한다.
(참고로 synchronized 라는 키워드는 운영체제 시간에 나왔었다.)
static class SynchronizedCollection<E> implements Collection<E>, Serializable {
@java.io.Serial
private static final long serialVersionUID = 3053995032091335093L;
@SuppressWarnings("serial") // Conditionally serializable
final Collection<E> c; // Backing Collection
@SuppressWarnings("serial") // Conditionally serializable
final Object mutex; // Object on which to synchronize
SynchronizedCollection(Collection<E> c) {
this.c = Objects.requireNonNull(c);
mutex = this;
}
SynchronizedCollection(Collection<E> c, Object mutex) {
this.c = Objects.requireNonNull(c);
this.mutex = Objects.requireNonNull(mutex);
}
public int size() {
synchronized (mutex) {return c.size();}
}
....
}
이 클래스의 동작은 단순히 내부에 갖고 있는 모든 컬렉션의 동작을 mutex 로 감싸고 있다.
이때 stream, spliterator, iterator 의 경우 mutex 로 감싸고 있지 않기 때문에, 유저가 직접 동기화를 걸어주어야 한다.
여기에서 foreach 의 경우 mutex 로 감싸져 있는데 foreach 는 '메서드' 이고, stream, spliterator, iterator 는 객체를 반환하기 때문에 mutex 를 걸 수 없었다고 이해했다.
마지막으로 자바의 synchronized (mutex) 라는 코드가 어떻게 동기화를 하는지 복습하면서 글을 마무리하려고 한다.
Java synchronized
자바의 synchronized 키워드는 특정 구간이나 메서드를 임계 영역으로 만들어, 한번에 하나의 스레드만 접근할 수 있도록 제한하는 역할을 수행한다.
이 키워드는 메서드에 직접 붙여서 해당 메서드 전체 로직이 하나의 스레드에서만 돌아가도록 할 수도 있고, 코드 블럭에 사용하여 특정 코드 블럭을 임계 영역으로 만들 수도 있다.
public void clear() {
synchronized (mutex) {c.clear();}
}
제일 간단한 clear() 메서드의 경우 위와 같이 사용하였다.
mutex 에는 동기화될 객체가 들어간다.
SynchronizedCollection(Collection<E> c) {
this.c = Objects.requireNonNull(c);
mutex = this;
}
기본적으로는 위와 같이 컬렉션만 받으면 자기 자신을 mutex 에 넣어서 이 객체가 수행하는 모든 동작이 임계 구역에 오직 한번만 들어갈 수 있도록 제한한다.
즉, 객체 단위로 락을 건다.
여러 스레드에서 접근한다는 것은, 이 컬렉션 객체는 메모리에 오직 하나만 올라가 있고, 여러 스레드에서 메모리 공간에 적재된 이 객체에 접근한다는 것인데, synchronized 키워드를 사용하면 특정 스레드가 이 객체에 접근해서 함수를 돌리고 있을 때, 다른 스레드에서는 이 객체에 접근해서 메서드를 호출할 수 없도록 막는다.
만약 동기화를 위해 락을 걸지 않았다면 A 스레드는 add() 메서드를, B 스레드는 size() 메서드를 호출해서 읽고 쓰기를 동시에 수행할 수 있었을 것이고, 그렇다면 B 스레드는 데이터가 추가되었음에도 추가되기 전의 개수를 가지고 로직을 수행하는 문제가 발생할 수 있다.
하지만 이렇게 락을 걸어두면, A 스레드가 add() 메서드를 호출하기 위해 접근한 순간 락이 걸리고, 나머지 스레드는 이 컬렉션 객체에 접근할 수 없으므로 다른 모든 메서드를 호출할 수 없어 기다리게 된다.
synchronized 를 활용한 동기화 구현은 JVM에 의해 수행되며, monitor 방식으로 동작한다.
이에 대해서는 다음 글에서 추가적으로 정리한다.
